| 记录编号 |
336485 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[WC 2006] 水管局长 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.552 s |
| 提交时间 |
2016-11-03 10:15:08 |
内存使用 |
4.52 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdarg>
#include <cstring>
#include <string>
#include <iostream>
#include <list>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
#define INF 0x3f3f3f3f
#define BETTER_CODE __attribute__((optimize("O3")))
struct node
{
node *ch[2], *f;
#define LC ch[0]
#define RC ch[1]
int rev;
node *maxson;
int value;
int id;
node():rev(0){}
BETTER_CODE
void pushdown()
{
if(rev)
{
LC -> rev ^= 1;
RC -> rev ^= 1;
swap(LC, RC);
rev = 0;
}
}
BETTER_CODE
void pushup()
{
maxson = this;
if(LC->maxson->value > maxson->value)
maxson = LC->maxson;
if(RC->maxson->value > maxson->value)
maxson = RC->maxson;
}
BETTER_CODE
void setv(int v)
{
value = v;
pushup();
}
}null_node;
BETTER_CODE
node *make_null()
{
null_node.LC = null_node.RC = null_node.f = &null_node;
null_node.id = 0;
null_node.maxson = &null_node;
null_node.value = -INF;
return &null_node;
}
node *null = make_null();
BETTER_CODE
inline node *new_node()
{
node *d = new node;
d -> LC = d -> RC = d -> f = null;
d -> maxson = null;
d -> value = -INF;
return d;
}
inline bool is_root(node *t)
{
return t == null || (t->f->LC != t && t->f->RC != t);
}
BETTER_CODE
void rotate(node *t)
{
if(is_root(t))return;
node *m = t->f;
if(!is_root(m))
{
if(m == m->f->LC)
m->f->LC = t;
else m->f->RC = t;
}
t->f = m->f;
int d = (t == m->RC);
m->ch[d] = t->ch[d^1];
if(t->ch[d^1] != null)t->ch[d^1]->f = m;
t->ch[d^1] = m;
m->f = t;
m->pushup();
t->pushup();
}
BETTER_CODE
void splay(node *t)
{
t->pushdown();
while(!is_root(t))
{
node *m = t->f;
m->f->pushdown();
m->pushdown();
t->pushdown();
if(is_root(m))
rotate(t);
else
{
if(t == m->f->LC->LC || t == m->f->RC->RC)
rotate(m);
else
rotate(t);
rotate(t);
}
}
t -> pushup();
}
BETTER_CODE
void access(node *t)
{
node *m = null;
while(t != null)
{
splay(t);
t->RC=m;
if(m != null)m->f = t;
t->pushup();
m = t;
t = t->f;
}
}
inline void make_root(node *t)
{
access(t);
splay(t);
t->rev ^= 1;
}
inline void cut(node *t)
{
access(t);
splay(t);
t->LC = t->LC->f = null;
t->pushup();
}
inline void cut(node *t, node *m)
{
make_root(t);
access(m);
splay(m);
m->LC = t->f = null;
}
inline void link(node *t, node *m)
{
make_root(t);
t->f = m;
access(t);
}
node *get_root(node *t)
{
access(t);
splay(t);
while(t->LC != null)t = t->LC;
return t;
}
int query_maxid(node *x, node *y)
{
make_root(x);
access(y);
splay(y);
return y->maxson->id;
}
BETTER_CODE
inline int fast_read()
{
char c;
int r;
while(c = getchar())
{
if(c >= '0' && c <= '9')
{
r = c^0x30;
break;
}
}
while(isdigit(c = getchar()))
r = (r<<3)+(r<<1)+(c^0x30);
return r;
}
struct edge
{
short from, to;
int value;
int id;
bool del;
bool operator<(const edge &e)const
{
return value < e.value;
}
}edges[100001];
bool cmpid(const edge &e1, const edge &e2)
{
return e1.id < e2.id;
}
bool cmpuv(const edge &e1, const edge &e2)
{
return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}
int n, m, q;
node *ns[101001];
int f[101001];
int findf(int x)
{
return x==f[x]?x:f[x]=findf(f[x]);
}
BETTER_CODE
void kruskal()
{
int cnt = 0;
for(int i = 1; i <= n; i++)f[i] = i;
for(int i = 1; i <= m; i++)
{
if(!edges[i].del)
{
int x = edges[i].from;
int y = edges[i].to;
if(findf(x) != findf(y))
{
f[findf(x)] = findf(y);
link(ns[x], ns[i+n]);
link(ns[i+n], ns[y]);
if(++cnt == n-1)break;
}
}
}
}
struct que
{
int ans, id;
int k, u, v; //操作类型，两端点
}qs[100001];
BETTER_CODE
int finde(int u, int v)
{
int l = 1, r = m;
while(l <= r)
{
int mid = (l+r)>>1;
edge &e = edges[mid];
if(e.from < u || (e.from == u && e.to < v))
l = mid+1;
else if(e.from == u && e.to == v)return mid;
else r = mid-1;
}
return 0;
}
BETTER_CODE
int main()
{
freopen("tube.in", "r", stdin);
freopen("tube.out", "w", stdout);
n = fast_read();
m = fast_read();
q = fast_read();
for(int i = 1; i <= n+m; i++)
{
ns[i] = new_node();
ns[i] -> id = i;
}
for(int i = 1; i <= m; i++)
{
edge &e = edges[i];
e.from = fast_read();
e.to = fast_read();
e.value = fast_read();
if(e.from > e.to)swap(e.from, e.to);
}
sort(edges+1, edges+m+1);
for(int i = 1; i <= m; i++)
{
edges[i].id = i;
ns[i+n] -> value = edges[i].value;
ns[i+n] -> maxson = ns[i+n];
}
sort(edges+1, edges+1+m, cmpuv); //这里把边按端点排序，然后就可以二分查找..
for(int i = 1; i <= q; i++)
{
que &q = qs[i];
q.k = fast_read();
q.u = fast_read();
q.v = fast_read();
if(q.k == 2)
{
if(q.u > q.v)swap(q.u, q.v);
int t = finde(q.u, q.v);
edges[t].del = true;
q.id = edges[t].id;
}
}
sort(edges+1, edges+1+m, cmpid);
kruskal();
for(int i = q; i; i--)
{
que &q = qs[i];
if(q.k == 1)
q.ans = ns[query_maxid(ns[q.u], ns[q.v])] -> value;
else
{
// printf("%d %d\n", q.u, q.v);
int u = q.u, v = q.v;
int k = q.id;
int t = query_maxid(ns[u], ns[v]);
if(edges[k].value < ns[t]->value)
{
cut(ns[edges[t-n].from], ns[t]);
cut(ns[edges[t-n].to], ns[t]);
link(ns[u], ns[k+n]);
link(ns[k+n], ns[v]);
}
}
}
for(int i = 1; i <= q; i++)
if(qs[i].k == 1)
printf("%d\n", qs[i].ans);
return 0;
}