QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369206#7608. CliquesDelay_for_five_minutes#WA 165ms44908kbC++203.2kb2024-03-27 21:56:302024-03-27 21:56:31

Judging History

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

  • [2024-03-27 21:56:31]
  • 评测
  • 测评结果:WA
  • 用时:165ms
  • 内存:44908kb
  • [2024-03-27 21:56:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
vector<int> E[200005];
const int mod = 1e9 + 7;
    const int N = 200005;
int n , q;
struct hld {
    
        int tag[N * 4];
        int sum[N * 4];
        void build(int u,int l,int r) {
            tag[u] = 1 ; sum[u] = (r - l + 1);
            if(l == r) return ;
            build(u<<1 , l , (l + r >> 1));
            build(u<<1|1 , (l + r >> 1) + 1 , r) ;
            return ;
        }
        void apply(int u,int v) {
            tag[u] = 1LL * tag[u] * v % mod;
            sum[u] = 1LL * sum[u] * v % mod;
        }
        void pd(int u) {
            if(tag[u] != 1) {
                apply(u<<1 , tag[u]);
                apply(u<<1|1 , tag[u]);
                tag[u] = 1;
            }
        }
        void modify(int u,int l,int r,int ql,int qr,int v) {
            if(ql <= l && qr >= r) {
                apply(u , v);
                return ;
            }
            int md = (l + r>>1);
            pd(u) ;
            if(ql <= md) modify(u<<1 , l , md , ql , qr , v);
            if(qr > md) modify(u<<1|1 , md + 1 , r , ql , qr , v);
            sum[u] = (sum[u << 1] + sum[u << 1|1]) % mod;
            return ;
        }
        
    int fa[N] , sz[N] , sn[N] , tp[N] , dfn[N] , nfd[N] , dep[N] , id;
    hld() {id = 0;}
    void dfs1(int u,int f) {
        sz[u] = 1; fa[u] = f;
        for(auto v : E[u]) {
            if(v != f) {
                dep[v] = dep[u] + 1;
                dfs1(v , u) ; sz[u] += sz[v] ;
                if(sz[sn[u]] < sz[v]) sn[u] = v;
            }
        }
    }
    void dfs2(int u,int p) {
        dfn[u] = ++id ; nfd[id] = u ; tp[u] = p;
        if(sn[u]) dfs2(sn[u] , p) ;
        for(auto v : E[u]) {
            if(v != fa[u] && v != sn[u]) dfs2(v , v);
        }
    }
    int lca(int x,int y) {
        while(tp[x] ^ tp[y]) {
            if(dep[tp[x]] < dep[tp[y]]) swap(x , y);
            x = fa[tp[x]] ;
        }
        if(dep[x] > dep[y]) swap(x , y) ;
        return x;
    }
    void mdf(int x,int y,int v) {
        while(tp[x] ^ tp[y]) {
            if(dep[tp[x]] < dep[tp[y]]) swap(x , y);
            modify(1 , 1 , n , dfn[x] , dfn[y] , v);
            x = fa[tp[x]] ;
        }
        if(dep[x] > dep[y]) swap(x , y);
        modify(1 , 1 , n , dfn[x] , dfn[y] , v) ;
    }
}A , B;

int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    cin >> n;
    for(int i = 1;i < n;i++) {
        int u , v;cin >> u >> v;
        E[u].push_back(v) ; E[v].push_back(u) ;
    }
    A.dfs1(1 , 0) ; A.dfs2(1 , 1); A.build(1 , 1 , n);
    B.dfs1(1 , 0) ; B.dfs2(1 , 1); B.build(1 , 1 ,n);
    cin >> q;
    int r2 = (mod + 1) / 2;
    while(q--) {
        char ch ; int u , v;
        cin >> ch  >> u >> v;
        if(ch == '+') {
            A.mdf(u , v , 2);
            B.mdf(u , v , 2);
            int l = B.lca(u , v);
            B.mdf(l , l , r2) ;
        }
        else {
            A.mdf(u , v , r2);
            B.mdf(u , v, r2);
            int l = B.lca(u , v);
            B.mdf(l , l , 2) ;
        }
        int ans = (A.sum[1] - B.sum[1] + mod ) % mod;
        cout << ans << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 22040kb

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: -100
Wrong Answer
time: 165ms
memory: 44908kb

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
3
5
10
20
36
52
104
200
328
360
720
912
1680
1682
2210
3746
3748
7364
6276
12484
12356
14468
22660
43140
47364
90372
84100
166020
168068
299140
598148
663684
1327236
2654340
2658436
2658440
5316872
5841160
11674120
11674122
22168074
22692362
21840138
43680010
43680012
43745548
43745549
43745553
...

result:

wrong answer 3rd lines differ - expected: '4', found: '3'