F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4012 >> 无故CE
Mychael @ 2018-05-18 20:42:55
[ Quote ] [ Edit ] [ Delete ] 1#
开-Wall连警告都没有。交洛谷可以正常跑,在BZOJ无论如何都CE
Mychael @ 2018-05-18 20:43:05
[ Quote ] [ Edit ] [ Delete ] 2#
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 100005,maxm = 200005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct heap{
priority_queue<int> a,b;
void ins(int x){if (x >= 0) a.push(x);}
void del(int x){if (x >= 0) b.push(x);}
int size(){return a.size() - b.size();}
int top(){
if (!size()) return -1;
while (!b.empty() && a.top() == b.top()) a.pop(),b.pop();
return a.top();
}
int sum(){
if (size() < 2) return -1;
int x = top(); a.pop();
int y = top(); ins(x);
return x + y;
}
}C[maxn],B[maxn],A;
int bin[50],Log[maxm],mn[maxm][19];
int n,fa[maxn],dep[maxn],dfn[maxn],cnt;
int h[maxn],ne = 1;
struct EDGE{int to,nxt;}ed[maxn << 1];
void build(int u,int v){
ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;
ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;
}
void dfs(int u){
mn[++cnt][0] = dep[u]; dfn[u] = cnt;
Redge(u) if ((to = ed[k].to) != fa[u]){
fa[to] = u; dep[to] = dep[u] + 1;
dfs(to);
mn[++cnt][0] = dep[u];
}
}
int dis(int u,int v){
int l = dfn[u],r = dfn[v];
if (l > r) swap(l,r);
int t = Log[r - l + 1];
int d = min(mn[l][t],mn[r - bin[t] + 1][t]);
return dep[u] + dep[v] - (d << 1);
}
int F[maxn],Siz[maxn],vis[maxn],Fa[maxn],sum,rt;
int pre[maxn];
void getrt(int u){
F[u] = 0; Siz[u] = 1;
Redge(u) if (!vis[to = ed[k].to] && to != Fa[u]){
Fa[to] = u; getrt(to);
Siz[u] += Siz[to];
F[u] = max(F[u],Siz[to]);
}
F[u] = max(F[u],sum - Siz[u]);
if (F[u] < F[rt]) rt = u;
}
int c[maxn],ci;
void dfs1(int u){
Siz[u] = 1; c[++ci] = u;
Redge(u) if (!vis[to = ed[k].to] && to != Fa[u]){
Fa[to] = u; dfs1(to);
Siz[u] += Siz[to];
}
}
void solve(int u){
vis[u] = true; Siz[u] = 1; ci = 0;
Redge(u) if (!vis[to = ed[k].to]){
Fa[to] = u; dfs1(to);
Siz[u] += Siz[to];
}
if (pre[u]){
C[u].ins(dis(u,pre[u]));
REP(i,ci) C[u].ins(dis(c[i],pre[u]));
}
Redge(u) if (!vis[to = ed[k].to]){
F[rt = 0] = INF; sum = Siz[to];
getrt(to);
pre[rt] = u; to = rt;
solve(rt);
B[u].ins(C[to].top());
}
B[u].ins(0);
A.ins(B[u].sum());
}
int light[maxn];
void Insert(int x){
int v;
A.del(B[x].sum());
B[x].ins(0);
A.ins(B[x].sum());
for (int u = x; pre[u]; u = pre[u]){
v = pre[u];
A.del(B[v].sum());
B[v].del(C[u].top());
C[u].ins(dis(x,v));
B[v].ins(C[u].top());
A.ins(B[v].sum());
}
}
void Delete(int x){
int v;
A.del(B[x].sum());
B[x].del(0);
A.ins(B[x].sum());
for (int u = x; pre[u]; u = pre[u]){
v = pre[u];
A.del(B[v].sum());
B[v].del(C[u].top());
C[u].del(dis(x,v));
B[v].ins(C[u].top());
A.ins(B[v].sum());
}
}
int main(){
bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = bin[i - 1] << 1;
Log[0] = -1; for (int i = 1; i < maxm; i++) Log[i] = Log[i >> 1] + 1;
n = read();
for (int i = 1; i < n; i++)
build(read(),read());
dfs(1);
for (int j = 1; j <= 18; j++)
for (int i = 1; i <= cnt; i++){
if (i + bin[j] - 1 > cnt) break;
mn[i][j] = min(mn[i][j - 1],mn[i + bin[j - 1]][j - 1]);
}
F[rt = 0] = INF; sum = n;
getrt(1);
solve(rt);
int m = read(),v; char opt;
while (m--){
opt = getchar();
while (opt != 'G' && opt != 'C') opt = getchar();
if (opt == 'G'){
v = A.top();
printf("%d\n",v >= 0 ? v : -1);
}
else {
v = read();
light[v] ^= 1;
if (!light[v]) Insert(v);
else Delete(v);
}
}
return 0;
}
Joky_02 @ 2018-08-22 18:31:08
[ Quote ] [ Edit ] [ Delete ] 3#
无故ce +1
rilisoft @ 2018-08-22 19:43:45
[ Quote ] [ Edit ] [ Delete ] 4#
在bzoj的六元cpu上CE不是很正常的吗?
[Top] [Previous Page] [Next Page]

HOME Back