oj.uz

Submission #777346

# Submission time Handle Problem Language Result Execution time Memory
777346 2023-07-09T06:28:03 Z ETO_leader Regions (IOI09_regions) C++17
6 / 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(col[i]>sqr){
        idx[i]=cx.size();cx.push_back(VL(r+1));
        fill(w.begin(),w.end(),0);
        dfsx(1,i);
        cir(i,1,n+1) cx[idx[i]][col[i]]+=w[i];
    }
    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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Incorrect 23 ms 592 KB Output isn't correct
8 Incorrect 35 ms 720 KB Output isn't correct
9 Incorrect 51 ms 1704 KB Output isn't correct
10 Incorrect 142 ms 2516 KB Output isn't correct
11 Incorrect 157 ms 2184 KB Output isn't correct
12 Incorrect 248 ms 3812 KB Output isn't correct
13 Incorrect 255 ms 3320 KB Output isn't correct
14 Incorrect 218 ms 3124 KB Output isn't correct
15 Incorrect 201 ms 6792 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 631 ms 7888 KB Output isn't correct
2 Incorrect 1073 ms 7640 KB Output isn't correct
3 Incorrect 1175 ms 10548 KB Output isn't correct
4 Incorrect 2775 ms 128628 KB Output isn't correct
5 Runtime error 1325 ms 131072 KB Execution killed with signal 9
6 Runtime error 2637 ms 131072 KB Execution killed with signal 9
7 Runtime error 2566 ms 131072 KB Execution killed with signal 9
8 Runtime error 1747 ms 131072 KB Execution killed with signal 9
9 Runtime error 4106 ms 131072 KB Execution killed with signal 9
10 Runtime error 1600 ms 131072 KB Execution killed with signal 9
11 Runtime error 3761 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8039 ms 126792 KB Time limit exceeded
13 Runtime error 5236 ms 131072 KB Execution killed with signal 9
14 Runtime error 6335 ms 131072 KB Execution killed with signal 9
15 Runtime error 2779 ms 131072 KB Execution killed with signal 9
16 Runtime error 2506 ms 131072 KB Execution killed with signal 9
17 Runtime error 2675 ms 131072 KB Execution killed with signal 9