QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#315214#7608. Cliquesthomas_li#WA 0ms3796kbC++173.3kb2024-01-27 05:59:242024-01-27 05:59:25

Judging History

你现在查看的是最新测评结果

  • [2024-01-27 05:59:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3796kb
  • [2024-01-27 05:59:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MOD = 1e9+7,i2 = MOD/2+1;
signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	struct Seg{
		struct Node{
			int l,r,sum,lz;
		};
		vector<Node> seg;
		Seg(int n) : seg(4*n+50){build(1,0,n-1);}
		void build(int u, int l, int r){
			seg[u].l = l; seg[u].r = r;
			seg[u].sum = r-l+1;
			seg[u].lz = 1;
			if(l == r){
				return;
			}
			int mid = (l+r)/2;
			build(u*2,l,mid); build(u*2+1,mid+1,r);
		}
		int query(int u, int l, int r){
			if(seg[u].l == l && seg[u].r == r) return seg[u].sum;
			push(u);
			int mid = (seg[u].l+seg[u].r)/2;
			if(r <= mid) return query(u*2,l,r);
			else if(l > mid) return query(u*2+1,l,r);
			else return (query(u*2,mid,r)+query(u*2+1,mid+1,r))%MOD;
		}
		int query(int l, int r){
			return query(1,l,r);
		}
		void push(int u){
			if(seg[u].lz == 1) return;
			for(int v : vi{2*u,2*u+1}){
				seg[v].sum = (seg[v].sum*seg[u].lz)%MOD;
				seg[v].lz = (seg[v].lz*seg[u].lz)%MOD;
			}
			seg[u].lz = 1;
		}
		void upd(int u, int l, int r, int x){
			if(seg[u].l == l && seg[u].r == r){
				if(x == 0){
					seg[u].sum = (seg[u].sum*2)%MOD;
					seg[u].lz = (seg[u].lz*2)%MOD;
				} else{
					seg[u].sum = (seg[u].sum*i2)%MOD;
					seg[u].lz = (seg[u].lz*i2)%MOD;				
				}
				return;
			}
			push(u);
			int mid = (seg[u].l+seg[u].r)/2;
			if(r <= mid) upd(u*2,l,r,x);
			else if(l > mid) upd(u*2+1,l,r,x);
			else upd(u*2,l,mid,x),upd(u*2+1,mid+1,r,x);
			seg[u].sum = (seg[u*2].sum+seg[u*2+1].sum)%MOD;
		}
		void upd(int l, int r, int x){
			if(l > r) return;
			upd(1,l,r,x);
		}
	};
	int n; cin >> n;	
	vector<vi> adj(n);
	vi siz(n),big(n,-1),dep(n),par(n);
	rep(i,0,n-1){
		int a,b; cin >> a >> b;	
		a--; b--;
		adj[a].PB(b); adj[b].PB(a);	
	}
	auto dfs = [&](auto&& dfs, int u, int p)->void{
		siz[u] = 1; par[u] = p;
		for(int v : adj[u]) if(v != p){
			dep[v] = dep[u]+1;
			dfs(dfs,v,u);
			siz[u] += siz[v];
			if(big[u] == -1 || siz[big[u]] < siz[v]) big[u] = v;
		}
	};
	dfs(dfs,0,-1);
	vi top(n),in(n),out(n); int ti = 0;
	auto dfs1 = [&](auto&& dfs1, int u, int p, int tp)->void{
		top[u] = tp; in[u] = ti++;
		if(big[u] != -1) dfs1(dfs1,big[u],u,tp);
		for(int v : adj[u]) if(v != p && big[u] != v){
			dfs1(dfs1,v,u,v);
		}
		out[u] = ti-1;
	};
	dfs1(dfs1,0,-1,0);
	Seg st(n),ste(n);
	auto add = [&](int u, int v, int x){
		while(top[u] != top[v]){
			if(dep[top[u]] < dep[top[v]]) swap(u,v);	
			st.upd(in[top[u]],in[u],x);
			ste.upd(in[top[u]]+1,in[u],x);
			u = par[top[u]];
		}
		if(dep[u] > dep[v]) swap(u,v);
		st.upd(in[u],in[v],x);
		ste.upd(in[u]+1,in[v],x);
	};
	int q; cin >> q;	
	while(q--){
		char t; int u,v; cin >> t >> u >> v;
		u--; v--;
		if(t == '+'){
			add(u,v,0);
		} else{
			add(u,v,1);
		}
		int ans = st.seg[1].sum;
		ans = (ans-ste.seg[1].sum+MOD)%MOD;
		ans = (ans-2+MOD)%MOD;
		cout << ans << "\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

5
1 2
5 1
2 3
4 2
6
+ 4 5
+ 2 2
+ 1 3
- 2 2
+ 2 3
+ 4 4

output:

1
3
7
3
7
9

result:

ok 6 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3796kb

input:

20
8 7
19 10
12 14
3 16
17 13
7 10
5 6
1 9
15 12
5 2
16 13
3 11
20 14
18 6
1 14
16 20
11 10
3 4
20 6
30
+ 10 20
+ 14 20
+ 12 17
- 14 20
- 12 17
+ 4 6
+ 8 20
+ 3 6
- 10 20
+ 2 17
+ 1 16
+ 6 10
+ 9 10
+ 5 15
+ 7 8
- 7 8
+ 2 5
+ 3 18
+ 1 20
+ 8 16
- 3 18
- 5 15
+ 4 20
+ 14 16
- 4 6
+ 8 19
+ 4 7
- 1 16
...

output:

1000000006
1
7
3
1000000006
3
7
17
9
22
38
78
143
288
290
288
292
581
1093
1349
676
401
787
1555
777
794
876
492
756
380

result:

wrong answer 1st lines differ - expected: '1', found: '1000000006'