oj.uz

Submission #1050945

# Submission time Handle Problem Language Result Execution time Memory
1050945 2024-08-09T17:09:01 Z Ludissey Regions (IOI09_regions) C++17
75 / 100
 8000 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,250);
    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);
    timer=0;
    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 2 ms 344 KB Output is correct
6 Correct 10 ms 1880 KB Output is correct
7 Correct 15 ms 600 KB Output is correct
8 Correct 19 ms 1164 KB Output is correct
9 Correct 38 ms 7000 KB Output is correct
10 Correct 83 ms 2288 KB Output is correct
11 Correct 109 ms 2668 KB Output is correct
12 Correct 126 ms 7848 KB Output is correct
13 Correct 164 ms 2648 KB Output is correct
14 Correct 166 ms 3160 KB Output is correct
15 Correct 239 ms 47496 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 19840 KB Output is correct
2 Correct 758 ms 7920 KB Output is correct
3 Correct 1089 ms 46552 KB Output is correct
4 Correct 274 ms 12808 KB Output is correct
5 Correct 354 ms 41776 KB Output is correct
6 Correct 548 ms 24872 KB Output is correct
7 Correct 773 ms 31736 KB Output is correct
8 Correct 911 ms 104728 KB Output is correct
9 Correct 2000 ms 63724 KB Output is correct
10 Runtime error 255 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8079 ms 68904 KB Time limit exceeded
12 Correct 1852 ms 52092 KB Output is correct
13 Correct 2192 ms 68996 KB Output is correct
14 Correct 2107 ms 65184 KB Output is correct
15 Runtime error 203 ms 131072 KB Execution killed with signal 9
16 Runtime error 164 ms 131072 KB Execution killed with signal 9
17 Runtime error 196 ms 131072 KB Execution killed with signal 9