QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250131#7608. CliquesarashMLGWA 5ms12824kbC++144.8kb2023-11-12 21:35:432023-11-12 21:35:43

Judging History

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

  • [2023-11-12 21:35:43]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:12824kb
  • [2023-11-12 21:35:43]
  • 提交

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], 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; 
          pre(u);
          ch[v].pb({siz[u],u});
          siz[v] += siz[u];
     }
}

void dfs(int v){
     st[v] = ++now;
     for(int i=0; i<ll(ch[v].size()); i++){
          int u = ch[v][i].S;
          if (i == (ll(ch[v].size()))-1) up[u] = up[v]; 
          else up[u] = 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){
     if (ras[ind].lz == 1) return; 
     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){
     if (yal[ind].lz == 1) return;
     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;
               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);
                    updyal(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);
               if (st[v]+1 <= st[u]) updyal(1,1,n,st[v]+1,st[u],2);
          }
          else{
               int v,u; cin >> v >> u;
               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);
                    updyal(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);
               if (st[v]+1 <= st[u]) updyal(1,1,n,st[v]+1,st[u],inv);
          }
          cout << (ras[1].val + 2*mod - yal[1].val - 1) % mod << endl; 
     }

     return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5ms
memory: 12824kb

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
767
1535
2047
2303
1151
639
1279
2559
1279
1295
1375
735
991
495

result:

wrong answer 17th lines differ - expected: '259', found: '767'