oj.uz

Submission #55006

# Submission time Handle Problem Language Result Execution time Memory
55006 2018-07-05T19:23:29 Z dfistric Regions (IOI09_regions) C++14
55 / 100
 3453 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 = 200002;
const int SQ = 510;
 
int dp[MAXN][SQ + 1];
int rez[MAXN][SQ + 1];
int rezup[SQ + 1][MAXN];
int smece[SQ + 1];
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 13 ms 12664 KB Output is correct
2 Correct 13 ms 12728 KB Output is correct
3 Correct 14 ms 12812 KB Output is correct
4 Correct 17 ms 13112 KB Output is correct
5 Correct 19 ms 14032 KB Output is correct
6 Correct 32 ms 15468 KB Output is correct
7 Correct 45 ms 16408 KB Output is correct
8 Correct 52 ms 17692 KB Output is correct
9 Correct 87 ms 24732 KB Output is correct
10 Correct 115 ms 34972 KB Output is correct
11 Correct 125 ms 44612 KB Output is correct
12 Correct 249 ms 55828 KB Output is correct
13 Correct 228 ms 62980 KB Output is correct
14 Correct 323 ms 74972 KB Output is correct
15 Correct 277 ms 98880 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1155 ms 131072 KB Output is correct
2 Correct 1487 ms 131072 KB Output is correct
3 Correct 1731 ms 131072 KB Output is correct
4 Correct 432 ms 131072 KB Output is correct
5 Correct 330 ms 131072 KB Output is correct
6 Correct 982 ms 131072 KB Output is correct
7 Correct 1657 ms 131072 KB Output is correct
8 Correct 2057 ms 131072 KB Output is correct
9 Execution timed out 3453 ms 131072 KB Time limit exceeded (wall clock)
10 Runtime error 1908 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 2909 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2847 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3249 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 2475 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 2347 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2736 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 2571 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)