Submission #1136103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136103		m_bezrutchka	Regions (IOI09_regions)	C++20	100 / 100	4454 ms	35632 KiB

regions

// submitting julia_08's solution
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;
const int MAXR = 3e4 + 10;

int region[MAXN], pai[MAXN];

vector<int> adj[MAXN];
vector<int> regions_pre[MAXN], regions_pos[MAXN];

int pre[MAXN], pos[MAXN];

int n, r, q;

int t = 0;

void dfs(int v){

  pre[v] = ++ t;

  for(auto u : adj[v]){
    if(u != pai[v]) dfs(u);
  }

  pos[v] = t;

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> r >> q;

  cin >> region[1];

  for(int i=2; i<=n; i++){
    cin >> pai[i] >> region[i];
    adj[pai[i]].push_back(i);
  }

  dfs(1);

  for(int i=1; i<=n; i++){
    regions_pre[region[i]].push_back(pre[i]);
    regions_pos[region[i]].push_back(pos[i]);
  }

  for(int i=1; i<=r; i++){
    sort(regions_pre[i].begin(), regions_pre[i].end());
    sort(regions_pos[i].begin(), regions_pos[i].end());
  }

  while(q--){

    int r1, r2; cin >> r1 >> r2;

    ll ans = 0;

    /*cout << "pre: " << r1 << " = ";

    for(auto x : regions_pre[r1]) cout << x << " ";
    cout << "\n";

    cout << "pos: " << r1 << " =  ";

    for(auto x : regions_pos[r1]) cout << x << " " ;
    cout << "\n";

    cout << "pre: " << r2 << " = ";

    for(auto x : regions_pre[r2]) cout << x << " ";
    cout << "\n";

    cout << "pos: " << r2 << " =  ";

    for(auto x : regions_pos[r2]) cout << x << " " ;
    cout << "\n";*/

    int l = -1;

    for(int i=0; i<regions_pos[r1].size(); i++){

      while(l + 1 < (int) regions_pre[r2].size() && regions_pre[r2][l + 1] <= regions_pos[r1][i]) l ++;

      // cout << i << ": " << regions_pos[r1][i] << "\n";
      // cout << "l = " << l << " " << regions_pre[r2][l + 1] << "\n";

      ans += (l + 1);

    } // soma os caras com pre maior

    l = -1;

    for(int i=0; i<regions_pre[r1].size(); i++){

      while(l + 1 < (int) regions_pre[r2].size() && regions_pre[r2][l + 1] < regions_pre[r1][i]) l ++;

      // cout << i << ": " << regions_pre[r1][i] << "\n";
      // cout << "l = " << l << "\n";

      ans -= (l + 1);

    } // subtrai os caras com pos menor

    cout << ans << endl;

  }

  return 0;
}

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