oj.uz

Submission #1050939

# Submission time Handle Problem Language Result Execution time Memory
1050939 2024-08-09T17:04:00 Z Ludissey Regions (IOI09_regions) C++17
75 / 100
 3403 ms 131072 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

vector<vector<int>> child;
vector<int> parent;
vector<vector<int>> up;
vector<vector<int>> down;
unordered_map<int,int> conv;
vector<int> rg;
vector<vector<int>> pr;
int need;
int sq;
vector<int> tin;
vector<int> out;
int timer=0;

vector<int> setup_down(int x){
    vector<int> cv(sq);
    for (auto u : child[x]) {
        vector<int> v=setup_down(u);
        for (int i=0; i<sq; i++)
        {
            down[conv[rg[x]]][i]+=v[i];
            cv[i]+=v[i];
        }
    }
    if(conv[rg[x]]<sq){
        down[conv[rg[x]]][conv[rg[x]]]++;
        cv[conv[rg[x]]]++;
    }
    return cv;
}

void setup_up(int x, vector<int> rm){
    for (int i=0; i<sz(rm); i++)
    {
        up[conv[rg[x]]][i]+=rm[i];
    }
    if(conv[rg[x]]<sq){
        up[conv[rg[x]]][conv[rg[x]]]++;
        rm[conv[rg[x]]]++;
    }
    for (auto u : child[x]) setup_up(u,rm);
    return;
}

void setup_euler(int x){
    tin[x]=timer++;
    for (auto u : child[x]) setup_euler(u);
    out[x]=timer++;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,R,Q; cin >> N >> R >> Q;
    sq=min(R,500);
    child.resize(N);
    parent.resize(N);
    up.resize(R,vector<int>(sq));
    down.resize(R,vector<int>(sq));
    rg.resize(N);
    tin.resize(N);
    out.resize(N);
    pr.resize(R);
    cin >> rg[0]; rg[0]--;
    vector<pair<int,int>> cnt(R);
    pr[rg[0]].push_back(0);
    cnt[rg[0]].first++;
    for (int i = 1; i < N; i++)
    {
        cin >> parent[i] >> rg[i]; parent[i]--; rg[i]--;
        child[parent[i]].push_back(i);
        pr[rg[i]].push_back(i);
        cnt[rg[i]].first++;
    }
    for (int i = 0; i < R; i++) cnt[i].second=i;
    
    sort(all(cnt),[&](auto &aa, auto &bb){return aa>bb; });
    for (int i = 0; i < sz(cnt); i++)
    {
        conv[cnt[i].second]=i;
    }
    vector<int> ep(sq);
    setup_euler(0);
    setup_up(0,ep);
    setup_down(0);
    for (int i = 0; i < Q; i++)
    {
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        int sm=0;
        if(conv[e1]<sq){
            sm=up[conv[e2]][conv[e1]];
        }else if(conv[e2]<sq) {
            sm=down[conv[e1]][conv[e2]];
        }else{
            for (int k = 0; k < sz(pr[e1]); k++)
            {
                int in1=tin[pr[e1][k]], out1=out[pr[e1][k]];
                for (int j = 0; j < sz(pr[e2]); j++)
                {
                    int in2=tin[pr[e2][j]], out2=out[pr[e2][j]];
                    if(in1<in2&&out1>out2) sm++;
                }   
            }
            
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 14 ms 1880 KB Output is correct
7 Correct 13 ms 600 KB Output is correct
8 Correct 21 ms 1112 KB Output is correct
9 Correct 51 ms 8104 KB Output is correct
10 Correct 100 ms 2960 KB Output is correct
11 Correct 112 ms 2820 KB Output is correct
12 Correct 251 ms 11976 KB Output is correct
13 Correct 184 ms 2904 KB Output is correct
14 Correct 160 ms 3160 KB Output is correct
15 Correct 253 ms 47236 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 19852 KB Output is correct
2 Correct 740 ms 7928 KB Output is correct
3 Correct 1172 ms 48120 KB Output is correct
4 Correct 366 ms 22276 KB Output is correct
5 Correct 578 ms 76512 KB Output is correct
6 Correct 786 ms 44192 KB Output is correct
7 Correct 1103 ms 56156 KB Output is correct
8 Runtime error 297 ms 131072 KB Execution killed with signal 9
9 Correct 2357 ms 111724 KB Output is correct
10 Runtime error 92 ms 131072 KB Execution killed with signal 9
11 Correct 3403 ms 121052 KB Output is correct
12 Correct 2386 ms 87036 KB Output is correct
13 Correct 2571 ms 119280 KB Output is correct
14 Correct 2640 ms 112204 KB Output is correct
15 Runtime error 94 ms 131072 KB Execution killed with signal 9
16 Runtime error 98 ms 131072 KB Execution killed with signal 9
17 Runtime error 139 ms 131072 KB Execution killed with signal 9