oj.uz

Submission #1050430

# Submission time Handle Problem Language Result Execution time Memory
1050430 2024-08-09T09:26:19 Z Ludissey Regions (IOI09_regions) C++17
13 / 100
 847 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

vector<vector<int>> child;
vector<unordered_map<int,int>> kp;
vector<int> parent;
vector<int> rg;
vector<vector<int>> pr;
vector<vector<pair<int,int>>> qPR;
vector<unordered_map<int,bool>> qHAS;
vector<unordered_map<int,int>> mp;
vector<int> out;

int need;
int sq;

unordered_map<int,int> kpp(int x){
    vector<unordered_map<int,int>> mpVEC;
    unordered_map<int,int> ep;
    ep[rg[x]]=1;
    mpVEC.push_back(ep);
    for (auto u : child[x]) mpVEC.push_back(kpp(u));
    sort(all(mpVEC), [&](auto &aa, auto &bb){return sz(aa)>sz(bb);});  
    
    for (int i = 1; i < sz(mpVEC); i++)
    {
        for (auto u : mpVEC[i])
        {
            mpVEC[0][u.first]+=u.second;
        }
        
    }
    for (auto u : mpVEC[0]) mp[x][u.first]+=u.second;
    return move(mpVEC[0]);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N,R,Q; cin >> N >> R >> Q;
    child.resize(N);
    kp.resize(N);
    parent.resize(N);
    mp.resize(N);
    qHAS.resize(R);
    rg.resize(N);
    pr.resize(R);
    sq=600;
    cin >> rg[0]; rg[0]--;
    pr[rg[0]].push_back(0);
    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);
    }
    qPR.resize(R);
    out.resize(Q);
    kpp(0);
    for (int i = 0; i < Q; i++)
    {
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        int sm=0;
        for (auto x : pr[e1])
        {
            sm+=mp[x][e2];
        }
        cout << sm << endl;
    }
    
    return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 22 ms 6660 KB Output is correct
7 Correct 30 ms 3000 KB Output is correct
8 Correct 26 ms 4912 KB Output is correct
9 Correct 126 ms 66872 KB Output is correct
10 Correct 109 ms 19572 KB Output is correct
11 Correct 282 ms 52008 KB Output is correct
12 Runtime error 139 ms 131072 KB Execution killed with signal 9
13 Correct 353 ms 51312 KB Output is correct
14 Correct 847 ms 106792 KB Output is correct
15 Runtime error 125 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 131072 KB Execution killed with signal 9
2 Runtime error 222 ms 131072 KB Execution killed with signal 9
3 Runtime error 130 ms 131072 KB Execution killed with signal 9
4 Runtime error 148 ms 131072 KB Execution killed with signal 9
5 Runtime error 138 ms 131072 KB Execution killed with signal 9
6 Runtime error 158 ms 131072 KB Execution killed with signal 9
7 Runtime error 173 ms 131072 KB Execution killed with signal 9
8 Runtime error 136 ms 131072 KB Execution killed with signal 9
9 Runtime error 136 ms 131072 KB Execution killed with signal 9
10 Runtime error 149 ms 131072 KB Execution killed with signal 9
11 Runtime error 156 ms 131072 KB Execution killed with signal 9
12 Runtime error 186 ms 131072 KB Execution killed with signal 9
13 Runtime error 153 ms 131072 KB Execution killed with signal 9
14 Runtime error 179 ms 131072 KB Execution killed with signal 9
15 Runtime error 122 ms 131072 KB Execution killed with signal 9
16 Runtime error 96 ms 131072 KB Execution killed with signal 9
17 Runtime error 127 ms 131072 KB Execution killed with signal 9