Submission #979440

#	Time	Username	Problem	Language	Result	Execution time	Memory
979440		AlphaMale06	Regions (IOI09_regions)	C++17	0 / 100	4078 ms	66484 KiB

regions

#include <bits/stdc++.h>
 
using namespace std;
 
#define F first
#define S second
 
const int N = 2e5+3;
const int inf = 1e9;
vector<int> g[N];
set<pair<int, int>> answered;
map<pair<int, int>, int> answer;
int a[N], tin[N], tout[N], cnt[N];
vector<pair<int, int>> posin[N], posout[N];
vector<int> pos[N];
int timer=1;
 
void dfs(int v, int p){
    tin[v]=timer++;
    for(int to : g[v])dfs(to, v);
    tout[v]=timer++;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    cin >> a[1];
    cnt[a[1]]++;
    for(int i=2; i<=n; i++){
        int x;
        cin >> x >> a[i];
        cnt[a[i]]++;
        g[x].push_back(i);
    }
    dfs(1, 1);
    for(int i=1; i<=n; i++){
        pos[a[i]].push_back(i);
        posin[a[i]].push_back({tin[i], posin[a[i]].size()+1});
        posout[a[i]].push_back({tout[i], posout[a[i]].size()+1});
    }
    for(int i=1; i<=r; i++){
        posin[i].push_back({2*N, cnt[i]+1});
        posout[i].push_back({2*N, cnt[i]+1});
        posin[i].push_back({0, 0});
        posout[i].push_back({0, 0});
        sort(posin[i].begin(), posin[i].end());
        sort(posout[i].begin(), posout[i].end());
    }
    for(int i=1; i<=r; i++){
        for(int j=0; j<posin[i].size(); j++){
            posin[i][j].S=j;
            posout[i][j].S=j;
        }
    }
    for(int i=0; i<q; i++){
        int u, v;
        cin >> u >> v;
        if(answered.find({u, v})!=answered.end()){
            cout << answer[{u, v}] << endl;
            continue;
        }
        int ans=0;
      	assert(u!=v);
        if(cnt[u]>cnt[v]){ //gledas za svakog v na gore
            int col = a[u];
            for(int e : pos[v]){
                auto ptr = upper_bound(posin[col].begin(), posin[col].end(), make_pair(tin[e], inf));
                ans += (*ptr).S; //dodas sve kojima je tin manji
                ptr = upper_bound(posout[col].begin(), posout[col].end(), make_pair(tin[e], inf));
                ans -= (*ptr).S; //oduzmes sve kojima je i tout manji
            }
        }
        else{//gledas za svako u na dole
            int col = a[v];
            for(int e : pos[u]){
                auto ptr = upper_bound(posin[col].begin(), posin[col].end(), make_pair(tout[e], inf));
                ans += (*ptr).S;
                ptr = lower_bound(posin[col].begin(), posin[col].end(), make_pair(tin[e], -1));
                ans -= (*ptr).S;
            }
        }
        answered.insert({u, v});
        answer[{u, v}] = ans;
        cout << ans << endl;
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0; j<posin[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85