oj.uz

Submission #1050900

# Submission time Handle Problem Language Result Execution time Memory
1050900 2024-08-09T16:36:39 Z Ludissey Regions (IOI09_regions) C++17
11 / 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> setup_down(int x){
    vector<int> cv(sq);
    for (auto u : child[x]) {
        vector<int> v=setup_down(u);
        for (int i=0; i<sz(v); i++)
        {
            down[conv[rg[x]]][i]+=v[i];
            cerr<<conv[rg[x]]<<" ";
            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;
}

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);
    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_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]];
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
11.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 2 ms 344 KB Output is correct
4 Correct 11 ms 484 KB Output is correct
5 Correct 40 ms 344 KB Output is correct
6 Correct 370 ms 2388 KB Output is correct
7 Correct 417 ms 1400 KB Output is correct
8 Correct 721 ms 2200 KB Output is correct
9 Correct 2792 ms 8196 KB Output is correct
10 Correct 7480 ms 18068 KB Output is correct
11 Correct 7296 ms 16900 KB Output is correct
12 Execution timed out 8010 ms 23100 KB Time limit exceeded
13 Execution timed out 8042 ms 19444 KB Time limit exceeded
14 Execution timed out 8034 ms 17456 KB Time limit exceeded
15 Execution timed out 8031 ms 62672 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8060 ms 25752 KB Time limit exceeded
2 Execution timed out 8064 ms 19412 KB Time limit exceeded
3 Execution timed out 8100 ms 53444 KB Time limit exceeded
4 Execution timed out 8039 ms 37660 KB Time limit exceeded
5 Execution timed out 8051 ms 81224 KB Time limit exceeded
6 Execution timed out 8051 ms 56388 KB Time limit exceeded
7 Execution timed out 8058 ms 68024 KB Time limit exceeded
8 Runtime error 297 ms 131072 KB Execution killed with signal 9
9 Execution timed out 8026 ms 110304 KB Time limit exceeded
10 Runtime error 105 ms 131072 KB Execution killed with signal 9
11 Runtime error 7505 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8069 ms 96896 KB Time limit exceeded
13 Execution timed out 8016 ms 117488 KB Time limit exceeded
14 Execution timed out 8044 ms 111860 KB Time limit exceeded
15 Runtime error 95 ms 131072 KB Execution killed with signal 9
16 Runtime error 97 ms 131072 KB Execution killed with signal 9
17 Runtime error 158 ms 131072 KB Execution killed with signal 9