| 记录编号 |
325420 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
图的询问 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.348 s |
| 提交时间 |
2016-10-19 18:30:37 |
内存使用 |
0.79 MiB |
显示代码纯文本
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct node
{
node *ch[2];
#define LC ch[0]
#define RC ch[1]
node *f;
int size, rev;
int maxv;
int data;
int id;
node():size(1), rev(0)
{
f = LC = RC = NULL;
}
void pushup()
{
size = 1;
maxv = data;
for(int i = 0; i <= 1; i++)if(ch[i])
{
size += ch[i]->size;
maxv = max(maxv, ch[i]->maxv);
}
}
void pushdown()
{
if(rev)
{
for(int i = 0; i <= 1; i++)if(ch[i])ch[i]->rev ^= 1;
rev = 0;
swap(LC, RC);
}
}
void setv(int v)
{
data = v;
pushup();
}
}soilder, *null = &soilder;
node *new_node()
{
node *t = new node();
t -> LC = t -> RC = t -> f = null;
t -> maxv = -0x7ffffffe;
}
class lct
{
public:
inline bool is_root(node *t)
{
return t == null || !t->f || (t->f->LC != t && t->f->RC != t);
}
void rotate(node *t) //把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;
//以上 用t替代了m的位置
//-----------------------
//这是一个单旋转
int d = (t == m->RC);
m->ch[d] = t->ch[d^1];
if(t->ch[d^1])t->ch[d^1]->f = m; //注意多维护了一个"父节点"信息。
t->ch[d^1] = m;
m->f = t; //m成了t的子节点
m->pushup();
//-------------------------
//t成为了新的(这个子树的)根
t->pushup();
}
/*
void recalc(node *t)
{
stack<node *> s; //用一个栈，模拟递归顺序
s.push(t);
for(node *p = t; !is_root(p); p = p -> f)
s.push(p -> f);
while(s.size())
{
s.top() -> pushdown();
s.pop();
}
}
*/
void splay(node *t)
{
//recalc(t); //太慢了...
t -> pushdown();
while(!is_root(t))
{
node *m = t->f;
m -> f -> pushdown(); //从上往下的顺序pushdown
m -> pushdown();
t -> pushdown();
if(is_root(m)) //m已经是根了
rotate(t); //t向上单旋一次，到根
else
{
if(t == m->f->LC->LC || t == m->f->RC->RC) //t,m,m->f在一条线上
rotate(m); //也就是
// m->f m
// / / \
// m -> t m->f(呸，它已经不是m的父节点了)
// /
// t
else
rotate(t); //自行脑补
rotate(t);
}
}
t -> pushup();
}
node *access(node *t)
{
node *m = null;
while(t && t != null)
{
splay(t);
t -> RC = m; //最开始一次t的RC变成了null，就是断开了...
m -> f = t;
t -> pushup();
m = t;
t = t -> f;
}
return m;
}
inline void makeroot(node *t)
{
access(t);
splay(t);
t -> rev ^= 1;
}
inline void link(node *t, node *m) //连接后t是m的孩子节点
{
makeroot(t);
t -> f = m;
access(t);
}
inline void cut(node *t)
{
access(t);
splay(t);
t -> LC = t -> LC -> f = null;
t -> pushup();
}
bool is_connected(node *t, node *m)
{
while(t -> f != null)t = t -> f;
while(m -> f != null)m = m -> f;
return t == m;
}
node *get_root(node *x) //x节点所在树的根
{
access(x);
splay(x);
while(x -> LC != null)x = x -> LC;
splay(x);
return x;
}
}gg;
int fast_read()
{
int r;
char c;
bool sig = false;
while(c = getchar())
{
if(c >= '0' && c <= '9')
{
r = c^0x30;
break;
}else if(c == '-')sig = true;
}
while(isdigit(c = getchar()))
r = (r<<3)+(r<<1)+(c^0x30);
return sig? -r:r;
}
void clear(int t)
{
while(t--)getchar();
}
#define MAXN 15001
node *ns[MAXN];
struct edge
{
int from, to, value;
bool intree;
bool operator<(const edge& e) const
{
return value < e.value;
}
}edges[MAXN<<1];
int uset[MAXN];
int finds(int u){return u==uset[u]?u:uset[u]=finds(uset[u]);}
void kruskal(int n, int m)
{
int cnt = 0;
sort(edges+1, edges+1+m);
for(int i = 1; i <= n; i++)uset[i] = i;
for(int i = 1; i <= m; i++)
{
int a = edges[i].from;
int b = edges[i].to;
int x, y;
if((x = finds(a)) != (y = finds(b)))
{
uset[x] = y;
edges[i].intree = true;
if(++cnt == n-1)return;
}
}
}
int main()
{
freopen("heatwave.in", "r", stdin);
freopen("heatwave.out", "w", stdout);
int n, m, k;
n = fast_read();
m = fast_read();
k = fast_read();
for(int i = 1; i <= m; i++)
{
edge &e = edges[i];
e.from = fast_read();
e.to = fast_read();
e.value = fast_read();
e.intree = false;
}
kruskal(n, m);
null -> f = null;
null -> LC = null -> RC = null;
null -> size = 0;
null -> maxv = -0x7ffffffe;
for(int i = 1; i <= n; i++)
{
ns[i] = new_node();
ns[i] -> id = i;
}
for(int i = 1; i <= m; i++)
{
edge &e = edges[i];
if(e.intree)
{
node *t = new_node();
t -> setv(e.value);
gg.link(ns[e.from], t);
gg.link(t, ns[e.to]);
}
}
while(k--)
{
int x = fast_read();
int y = fast_read();
gg.makeroot(ns[x]);
gg.access(ns[y]);
printf("%d\n", gg.get_root(ns[y])->maxv);
}
return 0;
}