oj.uz

Submission #777349

# Submission time Handle Problem Language Result Execution time Memory
777349 2023-07-09T06:31:32 Z ETO_leader Regions (IOI09_regions) C++17
35 / 100
 7188 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(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 3 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 Correct 27 ms 624 KB Output is correct
8 Correct 25 ms 776 KB Output is correct
9 Correct 54 ms 1776 KB Output is correct
10 Correct 112 ms 2608 KB Output is correct
11 Correct 158 ms 2124 KB Output is correct
12 Correct 242 ms 3916 KB Output is correct
13 Correct 254 ms 3440 KB Output is correct
14 Correct 264 ms 3144 KB Output is correct
15 Correct 244 ms 6856 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 7840 KB Output is correct
2 Correct 943 ms 7628 KB Output is correct
3 Correct 979 ms 10548 KB Output is correct
4 Correct 2709 ms 128628 KB Output is correct
5 Runtime error 1270 ms 131072 KB Execution killed with signal 9
6 Runtime error 2571 ms 131072 KB Execution killed with signal 9
7 Runtime error 2532 ms 131072 KB Execution killed with signal 9
8 Runtime error 1775 ms 131072 KB Execution killed with signal 9
9 Runtime error 3844 ms 131072 KB Execution killed with signal 9
10 Runtime error 1607 ms 131072 KB Execution killed with signal 9
11 Runtime error 3408 ms 131072 KB Execution killed with signal 9
12 Runtime error 7188 ms 131072 KB Execution killed with signal 9
13 Runtime error 4937 ms 131072 KB Execution killed with signal 9
14 Runtime error 5539 ms 131072 KB Execution killed with signal 9
15 Runtime error 2659 ms 131072 KB Execution killed with signal 9
16 Runtime error 2253 ms 131072 KB Execution killed with signal 9
17 Runtime error 2610 ms 131072 KB Execution killed with signal 9