QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253169#7608. CliquesShayan86TL 0ms15976kbC++234.5kb2023-11-16 19:22:512023-11-16 19:22:51

Judging History

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

  • [2023-11-16 19:22:51]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:15976kb
  • [2023-11-16 19:22:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 50;
const ll Mod = 1e9 + 7;

int n, q, par[N], sz[N], head[N], st[N], timer, inv2;

vector<int> adj[N];

ll mod(ll a, ll b = Mod){
    while(a >= b) a -= b;
    return a;
}

ll power(ll a, ll b, ll md = Mod){
    ll ans = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) ans = ans * a % md;
    }
    return ans;
}

void pre(int v){
    if(par[v]) adj[v].erase(find(all(adj[v]), par[v]));
    sz[v] = 1;
    for(int u: adj[v]){
        par[u] = v; pre(u); sz[v] += sz[u];
    }
    for(int i = 1; i < adj[v].size(); i++) if(sz[adj[v][0]] < sz[adj[v][i]]) swap(adj[v][0], adj[v][i]);
}

void hld(int v){
    st[v] = timer++;
    for(int u: adj[v]){
        if(u == adj[v][0]) head[u] = head[v];
        else head[u] = u;
        hld(u);
    }
}

ll seg1[N*4], lz1[N*4];

void quex1(int id, ll x){
    seg1[id] = mod(seg1[id] * x);
    lz1[id] = mod(lz1[id] * x);
}

void relax1(int id){
    quex1(lid, lz1[id]);
    quex1(rid, lz1[id]);
    lz1[id] = 1;
}

void build1(int l = 0, int r = n, int id = 1){
    if(l+1 == r){
        lz1[id] = 1; seg1[id] = 1; return;
    }
    build1(l, mid, lid);
    build1(mid, r, rid);
    seg1[id] = r-l; lz1[id] = 1;
}

void upd1(int ql, int qr, ll x, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr){
        quex1(id, x); return;
    }
    if(qr <= l || r <= ql) return;

    relax1(id);
    upd1(ql, qr, x, l, mid, lid);
    upd1(ql, qr, x, mid, r, rid);
    seg1[id] = mod(seg1[lid] + seg1[rid]);
}

ll get1(int ql, int qr, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr) return seg1[id];
    if(qr <= l || r <= ql) return 0;
    relax1(id);
    return mod(get1(ql, qr, l, mid, lid) + get1(ql, qr, mid, r, rid));
}


ll seg2[N*4], lz2[N*4];

void quex2(int id, ll x){
    seg2[id] = mod(seg2[id] * x);
    lz2[id] = mod(lz2[id] * x);
}

void relax2(int id){
    quex2(lid, lz2[id]);
    quex2(rid, lz2[id]);
    lz2[id] = 1;
}

void build2(int l = 0, int r = n, int id = 1){
    if(l+1 == r){
        lz2[id] = 1; seg2[id] = 1; return;
    }
    build2(l, mid, lid);
    build2(mid, r, rid);
    seg2[id] = r-l; lz2[id] = 1;
}

void upd2(int ql, int qr, ll x, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr){
        quex2(id, x); return;
    }
    if(qr <= l || r <= ql) return;

    relax2(id);
    upd2(ql, qr, x, l, mid, lid);
    upd2(ql, qr, x, mid, r, rid);
    seg2[id] = mod(seg2[lid] + seg2[rid]);
}

ll get2(int ql, int qr, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr) return seg2[id];
    if(qr <= l || r <= ql) return 0;
    relax2(id);
    return mod(get2(ql, qr, l, mid, lid) + get2(ql, qr, mid, r, rid));
}

void upd(int ql, int qr, ll x, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr){
        quex1(id, x); quex2(id, x); return;
    }
    if(qr <= l || r <= ql) return;

    relax1(id); relax2(id);
    upd(ql, qr, x, l, mid, lid);
    upd(ql, qr, x, mid, r, rid);
    seg1[id] = mod(seg1[lid] + seg1[rid]);
    seg2[id] = mod(seg2[lid] + seg2[rid]);
}

void upd_path(int u, int v, int x){
    while(head[u] != head[v]){
        if(st[u] < st[v]) swap(u, v);
        upd(st[head[u]], st[u]+1, x);
        u = par[head[u]];
    }
    if(st[u] < st[v]) swap(u, v);
    upd1(st[v], st[u]+1, x);
    upd2(st[v]+1, st[u]+1, x);
}

int main(){
    fast_io;

    inv2 = power(2, Mod-2);

    cin >> n;

    int u, v;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    pre(1); head[1] = 1; hld(1);

    cin >> q;

    build1(); build2();

    while(q--){
        char t;
        cin >> t >> u >> v;

        if(t == '+') upd_path(u, v, 2);
        else upd_path(u, v, inv2);

        ll res = mod(get1(0, n) - get2(0, n) + Mod);
        cout << res << endl;
    }

}

详细

Test #1:

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

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

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
Time Limit Exceeded

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:


result: