QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222528#7608. Cliquesucup-team1516#WA 2ms4488kbC++146.7kb2023-10-21 17:31:072023-10-21 17:31:08

Judging History

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

  • [2023-10-21 17:31:08]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：4488kb
查看
  • [2023-10-21 17:31:07]
  • 提交

answer

#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

constexpr int mod = 1000000007;

void mpl(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}

void mrg(pair<int,int>&a,pair<int,int>b) {
    a.first = 1ll*a.first*b.first%mod;
    a.second = (1ll*a.second*b.first+b.second)%mod;
}

int f[200200],cnt[200200];

template <typename T>
struct LazySegmentTree {
    int n;
    vector<T> dat;
    vector<pair<int,int>>lazy;
    LazySegmentTree() {};
    LazySegmentTree(int N) {
        n = 1;
        while(n < N) {
            n *= 2;
        }
        dat.resize(n*2,0);
        lazy.resize(n*2,{1,0});
    }
    void eval(int k,int l,int r) {
        if(lazy[k] == make_pair(1,0)) return;
        if(k < n) {
            mrg(lazy[k*2],lazy[k]);
            mrg(lazy[k*2+1],lazy[k]);
        }
        dat[k] = (1ll*dat[k]*lazy[k].first+lazy[k].second)%mod;
        lazy[k] = {1,0};
    }
    void update(int a, int b, pair<int,int> x, int k, int l, int r) {
        eval(k,l,r);
        if(a <= l && r <= b) {
            mrg(lazy[k],x);
            eval(k,l,r);
        }
        else if(a < r && l < b) {
            update(a, b, x, k*2, l, (l+r)/2);
            update(a, b, x, k*2+1, (l+r)/2, r);
            dat[k] = (dat[k*2]+dat[k*2+1])%mod;
        }
    }
    void update(int a, int b, pair<int,int> x) {//[a,b)
        update(a, b, x, 1, 0, n);
    }
    T query_sub(int a, int b, int k, int l, int r) {
        eval(k,l,r);
        if (r <= a || b <= l) {
            return 0;
        }
        else if (a <= l && r <= b) {
            return dat[k];
        }
        else {
            T vl = query_sub(a, b, k*2, l, (l+r)/2);
            T vr = query_sub(a, b, k*2+1, (l+r)/2, r);
            return (vl+vr)%mod;
        }
    }
    T query(int a, int b) {//[a,b)
        return query_sub(a, b, 1, 0, n);
    }
};

struct HLD { // 根が 0 でない時に注意
    vector<int>p,sz,in,nxt;
    LazySegmentTree<int> bit;
    void dfs1(vector<vector<int>>&c,int v = 0) {
        sz[v] = 1;
        for(int &w:c[v]) {
            dfs1(c,w);
            sz[v] += sz[w];
            if(sz[w] > sz[c[v][0]]) {
                swap(w,c[v][0]);
            }
        }
    }
    void dfs2(vector<vector<int>>&c,int &t,int v = 0) {
        in[v] = t;
        t++;
        for(int w:c[v]) {
            if(w == c[v][0]) {
                nxt[w] = nxt[v];
            }
            else {
                nxt[w] = w;
            }
            dfs2(c,t,w);
        }
    }
    HLD(vector<int>A,vector<int>p,vector<vector<int>>c):p(p) {
        int N = A.size();
        sz.resize(N,0);
        dfs1(c);
        in.resize(N,0);
        nxt.resize(N,0);
        int t = 0;
        dfs2(c,t);
        vector<int>tmp(N);
        for(int i = 0; i < N; i++) {
            tmp[in[i]] = A[i];
        }
        LazySegmentTree<int>init(tmp.size());
        for(int i = 0; i < tmp.size(); i++) {
            init.update(i,i+1,{1,tmp[i]});
        }
        bit = init;
    }
    int lca(int u,int v) {
        while(true) {
            if(in[u] > in[v]) {
                swap(u,v);
            }
            if(nxt[u] == nxt[v]) {
                return u;
            }
            v = p[nxt[v]];
        }
    }
    void update(int v,int x) {
        bit.update(in[v],in[v]+1,{1,x});
    }
    void update2(int u,int v,int x) {
        int w = lca(u,v);
        int ans = 0;
        while(nxt[u] != nxt[w]) {
            bit.update(in[nxt[u]],in[u]+1,{x,0});
            u = p[nxt[u]];
        }
        bit.update(in[w],in[u]+1,{x,0});
        while(nxt[v] != nxt[w]) {
            bit.update(in[nxt[v]],in[v]+1,{x,0});
            v = p[nxt[v]];
        }
        bit.update(in[w]+1,in[v]+1,{x,0});
    }
    void update3(int u,int v,int x) {
        int w = lca(u,v);
        int ans = 0;
        while(nxt[u] != nxt[w]) {
            bit.update(in[nxt[u]],in[u]+1,{1,x});
            u = p[nxt[u]];
        }
        bit.update(in[w],in[u]+1,{1,x});
        while(nxt[v] != nxt[w]) {
            bit.update(in[nxt[v]],in[v]+1,{1,x});
            v = p[nxt[v]];
        }
        bit.update(in[w]+1,in[v]+1,{1,x});
    }
    long long query(int u,int v) {
        int w = lca(u,v);
        int ans = 0;
        while(nxt[u] != nxt[w]) {
            mpl(ans,bit.query(in[nxt[u]],in[u]+1));
            u = p[nxt[u]];
        }
        mpl(ans,bit.query(in[w],in[u]+1));
        while(nxt[v] != nxt[w]) {
            mpl(ans,bit.query(in[nxt[v]],in[v]+1));
            v = p[nxt[v]];
        }
        mpl(ans,bit.query(in[w]+1,in[v]+1));
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>>ki(n);
    for(int i = 0; i < n-1; i++) {
        int u,w;
        cin >> u >> w;
        u--;
        w--;
        ki[u].push_back(w);
        ki[w].push_back(u);
    }
    vector<int>p(n,-1);
    vector<vector<int>>c(n);
    vector<int>a(n);
    queue<int>que;
    que.push(0);
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        for(int i:ki[x]) {
            if(p[i] == -1 && i != 0) {
                que.push(i);
                p[i] = x;
                c[x].push_back(i);
            }
        }
    }
    f[0] = 1;
    for(int i = 1; i <= 200000; i++) {
        f[i] = 2ll*f[i-1]%mod;
    }
    HLD hld1(a,p,c);
    HLD hld2(a,p,c);
    int ans = 0;
    int q;
    cin >> q;
    while(q--) {
        char c;
        int u,v;
        cin >> c >> u >> v;
        u--;
        v--;
        int lc = hld1.lca(u,v);
        if(c == '+') {
            mpl(ans,hld1.query(u,v));
            hld1.update2(u,v,2);
            int x = hld2.query(lc,lc)-cnt[lc];
            mpl(ans,f[x]);
            hld1.update(lc,f[x]);
            hld2.update3(u,v,1);
            cnt[lc]++;
        }
        else {
            int x = hld2.query(lc,lc)-cnt[lc];
            mpl(ans,mod-f[x]);
            hld1.update(lc,mod-f[x]);
            hld2.update3(u,v,-1);
            cnt[lc]--;
            mpl(ans,hld1.query(u,v));
            hld1.update2(u,v,500000004);
        }
        cout << ans << endl;
    }
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4488kb

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: 2ms
memory: 4464kb

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
12
13
15
19
27
40
48
64
96
160
288
290
288
292
548
1060
1316
2548
3040
3424
4192
5680
5696
5776
6541
6797
7485

result:

wrong answer 4th lines differ - expected: '3', found: '12'
English 繁體中文 简体中文

Server Time: 2024-12-04 04:26:08 | OpenSource Project