Submission #1050430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050430		Ludissey	Regions (IOI09_regions)	C++17	13 / 100	847 ms	131072 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<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 / 15
• Subtask 2: 0 / 85