Submission #1050391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050391		Ludissey	Regions (IOI09_regions)	C++17	0 / 100	42 ms	31824 KiB

regions

#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
• Subtask 2: 0 / 85