oj.uz

Submission #1050928

# Submission time Handle Problem Language Result Execution time Memory
1050928 2024-08-09T17:00:10 Z Ludissey Regions (IOI09_regions) C++17
85 / 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=sqrt(R);
    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 1 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 4 ms 344 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 13 ms 600 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 21 ms 1880 KB Output is correct
10 Correct 53 ms 1368 KB Output is correct
11 Correct 88 ms 1776 KB Output is correct
12 Correct 101 ms 3152 KB Output is correct
13 Correct 186 ms 2068 KB Output is correct
14 Correct 473 ms 2648 KB Output is correct
15 Correct 601 ms 11748 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2541 ms 8860 KB Output is correct
2 Correct 2792 ms 6012 KB Output is correct
3 Correct 4862 ms 14424 KB Output is correct
4 Correct 176 ms 5796 KB Output is correct
5 Correct 262 ms 16912 KB Output is correct
6 Correct 420 ms 12240 KB Output is correct
7 Correct 533 ms 17332 KB Output is correct
8 Correct 674 ms 53760 KB Output is correct
9 Correct 2385 ms 39520 KB Output is correct
10 Correct 2972 ms 114772 KB Output is correct
11 Execution timed out 8058 ms 49944 KB Time limit exceeded
12 Correct 2177 ms 34984 KB Output is correct
13 Correct 2756 ms 44292 KB Output is correct
14 Correct 2495 ms 45016 KB Output is correct
15 Correct 4450 ms 102496 KB Output is correct
16 Runtime error 187 ms 131072 KB Execution killed with signal 9
17 Runtime error 226 ms 131072 KB Execution killed with signal 9