QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#250036#7608. CliquesarashMLGTL 134ms47552kbC++235.2kb2023-11-12 20:37:212023-11-12 20:37:21

Judging History

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

  • [2023-11-12 20:37:21]
  • 评测
  • 测评结果：TL
  • 用时：134ms
  • 内存：47552kb
查看
  • [2023-11-12 20:37:21]
  • 提交

answer

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define all(x)      x.begin(),x.end()
#define pb          push_back
using namespace std;
typedef long long ll; 

#define int long long
const int N = 2e5+7, mod = 1e9+7; 
vector<int> g[N];
vector<pair<int,int>> ch[N];
int mark[N], siz[N], h[N], par[N], st[N], up[N], now; 
struct dat{int val, lz;} ras[N<<2], yal[N<<2]; 

int power(int a, int b){
     int ans = 1; 
     while(b){
          if (b&1) ans = ans * a % mod; 
          b /= 2;
          a = a * a % mod; 
     }
     return ans;
}

void pre(int v){
     mark[v] = 1; 
     siz[v] = 1; 
     for(int u : g[v]){
          if (mark[u]) continue;
          par[u] = v; 
          h[u] = h[v] + 1; 
          pre(u);
          ch[v].pb({siz[u],u});
     }
}

void dfs(int v){
     st[v] = ++now;
     for(int i=0; i<ll(ch[v].size()); i++){
          int u = ch[v][i].S;
          up[u] = (i == 0 ? up[v] : u); 
          dfs(u); 
     }
}

void build(int ind, int l, int r){
     if (l == r){
          ras[ind].val = 1; 
          yal[ind].val = (l == 1 ? 0 : 1);
          ras[ind].lz = yal[ind].lz = 1;
          return;
     }
     int mid = (l+r)>>1;
     build(2*ind,l,mid);
     build(2*ind+1,mid+1,r);
     ras[ind].val = ras[2*ind].val + ras[2*ind+1].val;
     ras[ind].lz = 1; 
     yal[ind].val = yal[2*ind].val + yal[2*ind+1].val;
     yal[ind].lz = 1; 
}

void shiftras(int ind, int l, int r){
     ras[ind].val = ras[ind].val * ras[ind].lz % mod; 
     if (l != r){
          ras[2*ind].lz = ras[2*ind].lz * ras[ind].lz % mod; 
          ras[2*ind+1].lz = ras[2*ind+1].lz * ras[ind].lz % mod; 
     }
     ras[ind].lz = 1; 
}

void updras(int ind, int l, int r, int st, int en, int val){
     shiftras(ind,l,r); 
     if (l > en || st > r) return;
     if (l == r || (l >= st && r <= en)){
          ras[ind].val = ras[ind].val * val % mod; 
          if (l != r){
               ras[2*ind].lz = ras[2*ind].lz * val % mod; 
               ras[2*ind+1].lz = ras[2*ind+1].lz * val % mod;
          }
          return;
     }
     int mid = (l+r)>>1; 
     updras(2*ind,l,mid,st,en,val);
     updras(2*ind+1,mid+1,r,st,en,val);
     ras[ind].val = (ras[2*ind].val + ras[2*ind+1].val) % mod; 
}

void shiftyal(int ind, int l, int r){
     yal[ind].val = yal[ind].val * yal[ind].lz % mod; 
     if (l != r){
          yal[2*ind].lz = yal[2*ind].lz * yal[ind].lz % mod; 
          yal[2*ind+1].lz = yal[2*ind+1].lz * yal[ind].lz % mod; 
     }
     yal[ind].lz = 1; 
}

void updyal(int ind, int l, int r, int st, int en, int val){
     shiftyal(ind,l,r); 
     if (l > en || st > r) return;
     if (l == r || (l >= st && r <= en)){
          yal[ind].val = yal[ind].val * val % mod; 
          if (l != r){
               yal[2*ind].lz = yal[2*ind].lz * val % mod; 
               yal[2*ind+1].lz = yal[2*ind+1].lz * val % mod;
          }
          return;
     }
     int mid = (l+r)>>1; 
     updyal(2*ind,l,mid,st,en,val);
     updyal(2*ind+1,mid+1,r,st,en,val);
     yal[ind].val = (yal[2*ind].val + yal[2*ind+1].val) % mod; 
}

int32_t main(){
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);	

     int n; cin >> n; 
     for(int i=1; i<n; i++){
          int v,u; cin >> v >> u; 
          g[v].pb(u);
          g[u].pb(v); 
     }
     pre(1); 
     for(int i=1; i<=n; i++) sort(all(ch[i]));
     up[1] = 1; 
     dfs(1); 
     build(1,1,n);
     int inv = power(2,mod-2);
     int q; cin >> q; 
     while(q--){
          char x; cin >> x; 
          if (x == '+'){
               int v,u; cin >> v >> u;
               int uu = u, vv = v; 
               while(up[v] != up[u]){
                    if (st[up[u]] < st[up[v]]) swap(v,u);
                    updras(1,1,n,st[up[u]],st[u],2);
                    u = par[up[u]];
               }
               if (st[v] > st[u]) swap(v,u);
               updras(1,1,n,st[v],st[u],2);
               u = uu;
               v = vv;
               while(up[v] != up[u]){
                    if (st[up[u]] < st[up[v]]) swap(v,u);
                    updyal(1,1,n,st[up[u]],st[u],2);
                    u = par[up[u]];
               }
               if (st[v] > st[u]) swap(v,u);
               if (u != v) updyal(1,1,n,st[v]+1,st[u],2);
          }
          else{
               int v,u; cin >> v >> u;
               int uu = u, vv = v; 
               while(up[v] != up[u]){
                    if (st[up[u]] < st[up[v]]) swap(v,u);
                    updras(1,1,n,st[up[u]],st[u],inv);
                    u = par[up[u]];
               }
               if (st[v] > st[u]) swap(v,u);
               updras(1,1,n,st[v],st[u],inv);
               u = uu;
               v = vv;
               while(up[v] != up[u]){
                    if (st[up[u]] < st[up[v]]) swap(v,u);
                    updyal(1,1,n,st[up[u]],st[u],inv);
                    u = par[up[u]];
               }
               if (st[v] > st[u]) swap(v,u);
               if (u != v) updyal(1,1,n,st[v]+1,st[u],inv);
          }
          cout << (ras[1].val + mod - yal[1].val - 1) % mod << endl; 
     }

     return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 25984kb

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: 0
Accepted
time: 0ms
memory: 25968kb

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:

1
3
7
3
1
3
7
15
7
15
31
63
127
255
257
255
259
515
1027
1283
643
385
769
1537
769
785
865
481
737
369

result:

ok 30 lines

Test #3:

score: 0
Accepted
time: 134ms
memory: 47552kb

input:

131072
3641 72511
10338 18718
8949 15478
79108 62887
42154 28540
65359 102645
93744 48493
3277 103211
43542 61315
93315 118634
24021 57937
31034 436
30411 6208
1388 25159
93424 128520
119820 87281
5860 97559
59648 8225
57244 58766
119685 13716
130165 60958
79806 116338
97486 80167
101963 95499
51263...

output:

1
2
4
8
13
27
43
67
119
215
359
423
847
1167
1935
2447
2975
4511
5023
8639
6911
13759
12991
15103
23295
43775
47999
91647
85375
167295
169343
301695
600703
666239
1332351
2664575
2678911
2687103
5374207
5898495
11731455
11731967
22283263
22807551
21955327
43910399
43911423
44207359
44207360
44469504...

result:

ok 46368 lines

Test #4:

score: -100
Time Limit Exceeded

input:

131073
52869 122762
63296 22816
9889 23435
9452 109352
95210 125504
104234 105533
42422 123259
31189 77343
88679 25422
13860 61424
49617 27681
71743 44108
2612 55383
89088 79225
49508 86216
45176 26493
60940 104568
10733 11047
118351 29678
6184 107897
69675 73910
39495 78910
14871 125941
64731 68683...

output:

1
3
7
11
15
19
31
35
71
143
287
511
1023
1031
1991
1031
1287
1927
2055
3151
4687
4943
9295
17999
18959
37775
73759
74559
148031
148095
296191
151743
160063
110399
110463
127103
63615
63679
64191
90303
138431
212479
212607
423551
423583
426527
770591
865599
1054015
1794879
3587647
3587903
5168959
743...

result:
English 繁體中文 简体中文

服务器时间: 2024-12-03 06:23:46 | 开源项目