oj.uz

Submission #55180

# Submission time Handle Problem Language Result Execution time Memory
55180 2018-07-06T08:52:18 Z dfistric Regions (IOI09_regions) C++14
13 / 100
 1524 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 MAXQ = 25010;
const int SQ = 510;
 
int dp[25010][SQ + 1];
int rez[25010][SQ + 1];
int rezup[SQ + 1][25010];
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:29: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:96: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:97:9: note: in expansion of macro 'REP'
         REP(j, emp[b].size()) {
         ^~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11896 KB Output is correct
2 Correct 15 ms 11956 KB Output is correct
3 Correct 17 ms 12288 KB Output is correct
4 Correct 18 ms 12468 KB Output is correct
5 Correct 25 ms 13268 KB Output is correct
6 Correct 40 ms 14752 KB Output is correct
7 Correct 50 ms 15776 KB Output is correct
8 Correct 52 ms 16972 KB Output is correct
9 Correct 74 ms 23996 KB Output is correct
10 Correct 88 ms 34364 KB Output is correct
11 Correct 177 ms 43964 KB Output is correct
12 Correct 206 ms 55228 KB Output is correct
13 Correct 303 ms 62396 KB Output is correct
14 Runtime error 140 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 50 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 147 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 58 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 87 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 99 ms 91964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 250 ms 105024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 229 ms 128500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 87 ms 128500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1164 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 698 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 1524 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 233 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 266 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 355 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 172 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 167 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 1513 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)