oj.uz

Submission #1050391

# Submission time Handle Problem Language Result Execution time Memory
1050391 2024-08-09T09:02:51 Z Ludissey Regions (IOI09_regions) C++17
0 / 100
 42 ms 31824 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<int> out;

int need;
int sq;

unordered_map<int,int> kpp(int x){
    vector<unordered_map<int,int>> mpVEC;
    unordered_map<int,int> cmap;
    cmap[rg[x]]=1;
    mpVEC.push_back(cmap);
    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;
        }
        
    }
    if(sz(pr[rg[x]])<=sq) {
        for (auto u : qPR[rg[x]])
        {
            out[u.second]+=mpVEC[0][u.first];
        }
    }
    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);
    qHAS.resize(R);
    rg.resize(N);
    pr.resize(R);
    sq=100;
    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);
    for (int i = 0; i < Q; i++)
    {
        int e1,e2; cin >> e1>>e2; e1--; e2--;
        qPR[e1].push_back({e2,i});
        qHAS[e1][e2]=true;
    }
    
    kpp(0);
    for (int i = 0; i < R; i++)
    {
        if(sz(qPR[i])==0) continue;
        if(sz(pr[i])>sq){
            need=i;
            //out[qPR[i].second].push_back(dfs(0));
        }
    }
    
    for (int i = 0; i < Q; i++) cout << out[i] << endl;
    
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
9 Execution timed out 1 ms 1112 KB Time limit exceeded (wall clock)
10 Execution timed out 2 ms 1880 KB Time limit exceeded (wall clock)
11 Execution timed out 3 ms 2392 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 3412 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 3416 KB Time limit exceeded (wall clock)
14 Execution timed out 6 ms 4440 KB Time limit exceeded (wall clock)
15 Execution timed out 6 ms 5976 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 11 ms 11096 KB Time limit exceeded (wall clock)
2 Execution timed out 11 ms 11096 KB Time limit exceeded (wall clock)
3 Execution timed out 12 ms 13656 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 4952 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 6232 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 8280 KB Time limit exceeded (wall clock)
7 Execution timed out 12 ms 11352 KB Time limit exceeded (wall clock)
8 Execution timed out 24 ms 15704 KB Time limit exceeded (wall clock)
9 Execution timed out 25 ms 23640 KB Time limit exceeded (wall clock)
10 Execution timed out 33 ms 27688 KB Time limit exceeded (wall clock)
11 Execution timed out 33 ms 29844 KB Time limit exceeded (wall clock)
12 Execution timed out 36 ms 28348 KB Time limit exceeded (wall clock)
13 Execution timed out 29 ms 28272 KB Time limit exceeded (wall clock)
14 Execution timed out 42 ms 29768 KB Time limit exceeded (wall clock)
15 Execution timed out 32 ms 31824 KB Time limit exceeded (wall clock)
16 Execution timed out 32 ms 31588 KB Time limit exceeded (wall clock)
17 Execution timed out 32 ms 31312 KB Time limit exceeded (wall clock)