QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90540#5250. Combination LocksSolitaryDream#WA 4ms9428kbC++203.1kb2023-03-23 15:57:062023-03-23 15:57:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-23 15:57:07]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9428kb
  • [2023-03-23 15:57:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=1e5+50,M=1e7+50;
int Tr[M][2],mag[M],cnt[M],tol;
ll val[M];
int New(int v) {
    int x=++tol;cnt[x]=1;
    val[x]=v;mag[x]=rand();
    return x;
}
void Up(int x) {
    cnt[x]=cnt[Tr[x][0]]+cnt[Tr[x][1]]+1;
}
void rotate(int &x,int f) {
    int y=Tr[x][f];
    Tr[x][f]=Tr[y][!f];Tr[y][!f]=x;
    Up(x);Up(y);x=y;
}
void Insert(int &x,ll v) {
    if(!x) {x=New(v);return ;}
    int f=v>val[x];
    Insert(Tr[x][f],v);
    if(mag[Tr[x][f]]>mag[x]) rotate(x,f);
    Up(x);
}
int qry(int x,ll v) {
    int t=0;
    while(x) {
        if(v<=val[x]) t+=cnt[Tr[x][1]]+1,x=Tr[x][0];
        else x=Tr[x][1];
    }
    return t;
}
vector<pair<int,int>> E[N];
vector<pair<int,pair<int,ll>>> G[N];
bool mark[N];
int sz[N];
int Min,tot,rt;
int m;
void dfs1(int x,int fr) {
    sz[x]=1;
    for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
        dfs1(y,x);
        sz[x]+=sz[y];
    }
}
void dfs2(int x,int fr) {
    int mx=tot-sz[x];
    for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
        dfs2(y,x);
        mx=max(mx,sz[y]);
    }
    if(mx<Min) Min=mx,rt=x;
}
void dfs3(int x,int fr,int c,ll d) {
    G[x].push_back({rt,{c,d}});
    for(auto [y,v]: E[x]) if(y!=fr && !mark[y]) {
        dfs3(y,x,c,d+v);
    }
}
void divide(int x) {
    dfs1(x,0);
    Min=tot=sz[x];
    dfs2(x,0);
    mark[rt]=1;
    for(auto [y,v]: E[rt]) if(!mark[y]) {
        dfs3(y,rt,++m,v);
    }
    for(auto [y,v]: E[rt]) if(!mark[y]) {
        divide(y);
    }
}
int root[M];
pair<int,int> ed[N];
int V[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin >> n;
    FOR(i,2,n) {
        int x,y,v;
        cin >> x >> y >> v;
        ed[i-1]={x,y};
        V[i-1]=v;
        E[x].push_back({y,v});
        E[y].push_back({x,v});
    }
    m=n;
    divide(1);
    cin >> q;
    while(q--) {
        string s;
        cin >> s;
        if(s[0]=='+') {
            int x;
            ll r;
            cin >> x >> r;
            for(auto e: G[x]) {
                int z=e.first;
                auto [c,d]=e.second;
                if(r>d) {
                    Insert(root[z],r-d);
                    Insert(root[c],r-d);
                }
            }
            Insert(root[x],r);
        } else {
            int res=0;
            int id;
            cin >> id;
            auto [x,y]=ed[id];
            if(G[x].size()<G[y].size()) swap(x,y);
            for(int i=0; i<G[y].size(); ++i) {
                int z=G[y][i].first;
                auto [c,d]=G[y][i].second;
                d=max(d,G[x][i].second.second);
                res+=qry(root[z],d)-qry(root[c],d);
            }
            for(int i=G[y].size(); i<G[x].size(); ++i) {
                int z=G[x][i].first;
                auto [c,d]=G[x][i].second;
                if(y!=z) d+=V[id-1];
                res+=qry(root[z],d)-qry(root[c],d);
            }
            cout << res << '\n';
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 9428kb

input:

2
1 0
0
0
1 1
0
0
.

output:


result:

wrong answer 1st lines differ - expected: 'Alice', found: ''