oj.uz

Submission #724995

# Submission time Handle Problem Language Result Execution time Memory
724995 2023-04-16T12:22:44 Z FatihSolak Regions (IOI09_regions) C++17
100 / 100
 4209 ms 59440 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
const int magic = 500;
vector<int> adj[N];
int h[N];
int timer = 0;
int tot = 0;
int id[N];
int tin[N],tout[N];
int downval[N][N/magic + 5];
int upval[N][N/magic + 5];
int upcnt[N/magic + 5];
int sub[N];
vector<pair<int,int>> events[N];
vector<pair<int,int>> seq[N];
vector<int> nodes[N];
void dfs(int v){
    tin[v] = timer++;
    seq[tin[v]].push_back({h[v],1});
    nodes[h[v]].push_back(v);
    sub[v] = 1;
    for(auto u:adj[v]){
        dfs(u);
        sub[v] += sub[u];
    }
    tout[v] = timer;
    seq[tout[v]].push_back({h[v],-1});
}
vector<int> dfs2(int v){
    sort(adj[v].begin(),adj[v].end(),[&](int a,int b){
        return sub[a] > sub[b];
    });
    for(int i = 1;i<=tot;i++){
        upval[h[v]][i] += upcnt[i];
    }
    upcnt[id[h[v]]]++;
    vector<int> ret;
    for(auto u:adj[v]){
        if(ret.empty()){
            ret = dfs2(u);
        }
        else{
            auto tmp = dfs2(u);
            for(int i = 0;i<=tot;i++){
                ret[i] += tmp[i];
            }
        }
    }
    upcnt[id[h[v]]]--;
    if(ret.empty()){
        ret.assign(tot + 1,0);
    }
    for(int i = 1;i<=tot;i++){
        downval[h[v]][i] += ret[i];
    }
    return ret;
}

void solve(){
    int n,r,q;
    cin >> n >> r >> q;
    for(int i = 1;i<=n;i++){
        if(i > 1){
            int x;
            cin >> x;
            adj[x].push_back(i);
        }
        cin >> h[i];
    }
    for(int i = 1;i<=r;i++){
        if(nodes[i].size() > magic){
            id[i] = ++tot;
        }
    }
    dfs(1);
    dfs2(1);
    for(int i = 0;i<=n;i++){
        for(auto u:seq[i]){
            events[u.first].push_back({i,u.second});
        }
    }
    for(int i = 1;i<=q;i++){
        int r1,r2;
        cin >> r1 >> r2;
        if(id[r2] != 0){
            cout << downval[r1][id[r2]] << endl;
            continue;
        }
        if(id[r1] != 0){
            cout << upval[r2][id[r1]] << endl;
            continue;
        }
        int ans = 0;
        int cnt = 0;
        int pt = 0;
        for(auto u:nodes[r2]){
            while(pt != events[r1].size() && events[r1][pt].first <= tin[u]){
                cnt += events[r1][pt].second;
                pt++;
            }
            ans += cnt;
        }
        cout << ans << endl;
    }
}

int main(){
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(pt != events[r1].size() && events[r1][pt].first <= tin[u]){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19024 KB Output is correct
2 Correct 10 ms 19020 KB Output is correct
3 Correct 12 ms 19008 KB Output is correct
4 Correct 13 ms 19024 KB Output is correct
5 Correct 14 ms 19152 KB Output is correct
6 Correct 31 ms 19276 KB Output is correct
7 Correct 43 ms 19284 KB Output is correct
8 Correct 25 ms 19280 KB Output is correct
9 Correct 61 ms 20176 KB Output is correct
10 Correct 96 ms 20252 KB Output is correct
11 Correct 124 ms 20944 KB Output is correct
12 Correct 139 ms 21968 KB Output is correct
13 Correct 134 ms 21540 KB Output is correct
14 Correct 213 ms 22764 KB Output is correct
15 Correct 235 ms 27592 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2347 ms 29020 KB Output is correct
2 Correct 4034 ms 27376 KB Output is correct
3 Correct 3952 ms 32684 KB Output is correct
4 Correct 323 ms 22728 KB Output is correct
5 Correct 310 ms 25732 KB Output is correct
6 Correct 632 ms 25288 KB Output is correct
7 Correct 963 ms 27508 KB Output is correct
8 Correct 968 ms 37008 KB Output is correct
9 Correct 1611 ms 39124 KB Output is correct
10 Correct 2095 ms 47568 KB Output is correct
11 Correct 2464 ms 40152 KB Output is correct
12 Correct 1758 ms 41492 KB Output is correct
13 Correct 2408 ms 42212 KB Output is correct
14 Correct 2555 ms 41976 KB Output is correct
15 Correct 3367 ms 49180 KB Output is correct
16 Correct 4209 ms 59440 KB Output is correct
17 Correct 3546 ms 58016 KB Output is correct