oj.uz

Submission #777347

# Submission time Handle Problem Language Result Execution time Memory
777347 2023-07-09T06:29:29 Z ETO_leader Regions (IOI09_regions) C++17
20 / 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;
        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 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 17 ms 336 KB Output is correct
7 Correct 22 ms 592 KB Output is correct
8 Correct 25 ms 812 KB Output is correct
9 Correct 57 ms 1784 KB Output is correct
10 Correct 158 ms 2572 KB Output is correct
11 Correct 214 ms 2152 KB Output is correct
12 Correct 279 ms 3924 KB Output is correct
13 Correct 448 ms 3436 KB Output is correct
14 Correct 815 ms 3224 KB Output is correct
15 Correct 719 ms 6704 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8012 ms 7780 KB Time limit exceeded
2 Execution timed out 8103 ms 7528 KB Time limit exceeded
3 Execution timed out 8004 ms 10500 KB Time limit exceeded
4 Correct 2877 ms 128644 KB Output is correct
5 Runtime error 1322 ms 131072 KB Execution killed with signal 9
6 Runtime error 2631 ms 131072 KB Execution killed with signal 9
7 Runtime error 2566 ms 131072 KB Execution killed with signal 9
8 Runtime error 1793 ms 131072 KB Execution killed with signal 9
9 Runtime error 3867 ms 131072 KB Execution killed with signal 9
10 Runtime error 1675 ms 131072 KB Execution killed with signal 9
11 Runtime error 3581 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8105 ms 130696 KB Time limit exceeded
13 Runtime error 5395 ms 131072 KB Execution killed with signal 9
14 Runtime error 6386 ms 131072 KB Execution killed with signal 9
15 Runtime error 2657 ms 131072 KB Execution killed with signal 9
16 Runtime error 2324 ms 131072 KB Execution killed with signal 9
17 Runtime error 2708 ms 131072 KB Execution killed with signal 9