oj.uz

Submission #55005

# Submission time Handle Problem Language Result Execution time Memory
55005 2018-07-05T19:19:28 Z dfistric Regions (IOI09_regions) C++14
55 / 100
 3102 ms 131072 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12664 KB Output is correct
2 Correct 13 ms 12728 KB Output is correct
3 Correct 17 ms 12792 KB Output is correct
4 Correct 16 ms 13048 KB Output is correct
5 Correct 22 ms 13996 KB Output is correct
6 Correct 31 ms 15532 KB Output is correct
7 Correct 56 ms 16700 KB Output is correct
8 Correct 60 ms 18040 KB Output is correct
9 Correct 89 ms 25848 KB Output is correct
10 Correct 160 ms 36856 KB Output is correct
11 Correct 200 ms 47524 KB Output is correct
12 Correct 237 ms 59940 KB Output is correct
13 Correct 265 ms 67752 KB Output is correct
14 Correct 269 ms 80828 KB Output is correct
15 Correct 321 ms 107196 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1230 ms 131072 KB Output is correct
2 Correct 1252 ms 131072 KB Output is correct
3 Correct 1931 ms 131072 KB Output is correct
4 Correct 426 ms 131072 KB Output is correct
5 Correct 526 ms 131072 KB Output is correct
6 Correct 1143 ms 131072 KB Output is correct
7 Correct 1814 ms 131072 KB Output is correct
8 Correct 2088 ms 131072 KB Output is correct
9 Runtime error 3102 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 2049 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 2762 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2473 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3091 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 2141 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 2405 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2333 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 2093 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)