oj.uz

Submission #1050915

# Submission time Handle Problem Language Result Execution time Memory
1050915 2024-08-09T16:47:31 Z Ludissey Regions (IOI09_regions) C++17
30 / 100
 2578 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<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;
}

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
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 11 ms 1880 KB Output is correct
7 Correct 15 ms 600 KB Output is correct
8 Correct 23 ms 1112 KB Output is correct
9 Correct 57 ms 8104 KB Output is correct
10 Correct 93 ms 2900 KB Output is correct
11 Correct 109 ms 2732 KB Output is correct
12 Correct 241 ms 11824 KB Output is correct
13 Correct 188 ms 2648 KB Output is correct
14 Correct 166 ms 2904 KB Output is correct
15 Correct 261 ms 46924 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 19320 KB Output is correct
2 Correct 728 ms 7312 KB Output is correct
3 Correct 1217 ms 47516 KB Output is correct
4 Incorrect 369 ms 22040 KB Output isn't correct
5 Incorrect 591 ms 76316 KB Output isn't correct
6 Incorrect 756 ms 43708 KB Output isn't correct
7 Incorrect 1098 ms 55452 KB Output isn't correct
8 Runtime error 320 ms 131072 KB Execution killed with signal 9
9 Incorrect 2286 ms 110460 KB Output isn't correct
10 Runtime error 97 ms 131072 KB Execution killed with signal 9
11 Incorrect 2577 ms 119616 KB Output isn't correct
12 Incorrect 2296 ms 85492 KB Output isn't correct
13 Incorrect 2412 ms 117900 KB Output isn't correct
14 Incorrect 2578 ms 110596 KB Output isn't correct
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 151 ms 131072 KB Execution killed with signal 9