oj.uz

Submission #777350

# Submission time Handle Problem Language Result Execution time Memory
777350 2023-07-09T06:33:15 Z ETO_leader Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131072 KB 
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
using VI=vector<int>;
using VL=vector<lint>;
vector<VI> G;vector<VL> cx;
VI tin,tout,w,col;
void dfs(int u,int&cnx,int f=0){
    tin[u]=cnx++;
    for(auto&i:G[u]) if(i!=f) dfs(i,cnx,u);
    tout[u]=cnx;
}
bool isancestor(int u,int v){
    return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
void dfsx(int u,int ci,int wx=0,int f=0){
    w[u]=(wx+=(col[u]==ci));
    for(auto&i:G[u]) if(i!=f) dfsx(i,ci,wx,u);
}
void init(int n){
    G.resize(n+1);tin.resize(n+1);col.resize(n+1);
    tout.resize(n+1);w.resize(n+1);
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,r,q;cin>>n>>r>>q;init(n);
    const int sqr=pow<double>(n,3.0/1.0)+1;
    VL cnx(r+1),idx(n+1);
    vector<VI> ci(r+1);
    cin>>col[1];cnx[col[1]]++;ci[col[1]].push_back(1);
    cir(i,2,n+1){
        int f;cin>>f>>col[i];cnx[col[i]]++;
        G[f].push_back(i);G[i].push_back(f);
        ci[col[i]].push_back(i);
    }
    [&](){int ncnx=0;dfs(1,ncnx);}();
    cir(i,1,r+1) if(cnx[i]>sqr){
        idx[i]=cx.size();cx.push_back(VL(r+1));
        fill(w.begin(),w.end(),0);
        dfsx(1,i);
        cir(j,1,n+1) cx[idx[i]][col[j]]+=w[j];
    }
    auto bfdis=[&](int c1,int c2){
        lint res=0;
        for(auto&i:ci[c1]) for(auto&j:ci[c2])
            res+=isancestor(i,j);
        return res;
    };
    cir(i,0,q){
        int r1,r2;cin>>r1>>r2;
        if(cnx[r1]>sqr) cout<<cx[idx[r1]][r2]<<'\n';
        else if(cnx[r2]>sqr) cout<<cnx[r1]*cnx[r2]-cx[idx[r2]][r1]<<'\n';
        else cout<<bfdis(r1,r2)<<'\n';
        cout.flush();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 12 ms 336 KB Output is correct
7 Correct 28 ms 592 KB Output is correct
8 Correct 26 ms 720 KB Output is correct
9 Correct 50 ms 1672 KB Output is correct
10 Correct 120 ms 2508 KB Output is correct
11 Correct 161 ms 2216 KB Output is correct
12 Correct 247 ms 3916 KB Output is correct
13 Correct 273 ms 3404 KB Output is correct
14 Correct 271 ms 3232 KB Output is correct
15 Correct 212 ms 6808 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 7844 KB Output is correct
2 Correct 943 ms 7752 KB Output is correct
3 Correct 1281 ms 10544 KB Output is correct
4 Correct 2652 ms 128728 KB Output is correct
5 Runtime error 1362 ms 131072 KB Execution killed with signal 9
6 Runtime error 2574 ms 131072 KB Execution killed with signal 9
7 Runtime error 2552 ms 131072 KB Execution killed with signal 9
8 Runtime error 1924 ms 131072 KB Execution killed with signal 9
9 Runtime error 5108 ms 131072 KB Execution killed with signal 9
10 Runtime error 1772 ms 131072 KB Execution killed with signal 9
11 Runtime error 3648 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8036 ms 131072 KB Time limit exceeded
13 Runtime error 5271 ms 131072 KB Execution killed with signal 9
14 Runtime error 6046 ms 131072 KB Execution killed with signal 9
15 Runtime error 2524 ms 131072 KB Execution killed with signal 9
16 Runtime error 2230 ms 131072 KB Execution killed with signal 9
17 Runtime error 2574 ms 131072 KB Execution killed with signal 9