Submission #55005

#	Time	Username	Problem	Language	Result	Execution time	Memory
55005		dfistric	Regions (IOI09_regions)	C++14	55 / 100	3102 ms	131072 KiB

regions

#include <bits/stdc++.h>
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
 
using namespace std;
 
const int MAXN = 200100;
const int SQ = 510;
 
int dp[MAXN][SQ + 50];
int rez[MAXN][SQ + 50];
int rezup[SQ + 50][MAXN];
int smece[SQ + 50];
int rs[MAXN];
int reg[MAXN];
vector <int> arr;
vector <int> ve[MAXN];
vector <int> emp[MAXN];
int ind[MAXN];
int D[MAXN], F[MAXN], cnt = -1;
 
void dfs(int x, int par) {
  D[x] = ++cnt;
  if (ind[reg[x]] < SQ) smece[ind[reg[x]]]++;
 
  REP(i, ve[x].size()) {
    int ne = ve[x][i];
    if (ne == par) continue;
 
    dfs(ne, x);
    REP(j, SQ) {
      dp[x][j] += dp[ne][j];
    }
  }
  REP(j, SQ) {
    rez[ind[reg[x]]][j] += dp[x][j];
    rezup[j][ind[reg[x]]] += smece[j] - (j == ind[reg[x]]);
  }
 
  if (ind[reg[x]] < SQ) {
    dp[x][ind[reg[x]]]++;
    smece[ind[reg[x]]]--;
  }
  F[x] = cnt;
  return;
}
 
bool cmp(int a, int b) {
  if (rs[a] == rs[b]) return a < b;
  return rs[a] > rs[b];
}
 
int main() {
  ios_base::sync_with_stdio(false);
  
  int n, r, q;
  cin >> n >> r >> q;
 
  cin >> reg[0];
  reg[0]--;
  rs[reg[0]]++;
  REP(i, n - 1) {
    int x;
    cin >> x >> reg[i + 1];
    reg[i + 1]--;
    rs[reg[i + 1]]++;
    x--;
    ve[x].push_back(i + 1);
  }
  REP(i, r) arr.push_back(i);
  sort(arr.begin(), arr.end(), cmp);
 
  REP(i, r) ind[arr[i]] = i;
  REP(i, n) {
    int asd = ind[reg[i]];
    emp[asd].push_back(i);
  }
 
  dfs(0, 0);
 
  REP(k, q) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    a = ind[a];
    b = ind[b];
    if (b < SQ) {
      cout << rez[a][b] << endl;
    } else if (a < SQ) {
      cout << rezup[a][b] << endl;
    } else {
      int out = 0;
      REP(i, emp[a].size()) {
        REP(j, emp[b].size()) {
          int c = emp[a][i];
          int d = emp[b][j];
          if (D[c] < D[d] && D[d] <= F[c]) out++;
        }
      }
      cout << out << endl;
    }
  }
  
  return 0;
}
 

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i = (a); i < (b); i++)
                                          ^
regions.cpp:5:19: note: in expansion of macro 'FOR'
 #define REP(i, n) FOR(i, 0, n)
                   ^~~
regions.cpp:28:3: note: in expansion of macro 'REP'
   REP(i, ve[x].size()) {
   ^~~
regions.cpp: In function 'int main()':
regions.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i = (a); i < (b); i++)
                                          ^
regions.cpp:5:19: note: in expansion of macro 'FOR'
 #define REP(i, n) FOR(i, 0, n)
                   ^~~
regions.cpp:95:7: note: in expansion of macro 'REP'
       REP(i, emp[a].size()) {
       ^~~
regions.cpp:3:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i = (a); i < (b); i++)
                                          ^
regions.cpp:5:19: note: in expansion of macro 'FOR'
 #define REP(i, n) FOR(i, 0, n)
                   ^~~
regions.cpp:96:9: note: in expansion of macro 'REP'
         REP(j, emp[b].size()) {
         ^~~

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