oj.uz

Submission #55182

# Submission time Handle Problem Language Result Execution time Memory
55182 2018-07-06T08:53:35 Z dfistric Regions (IOI09_regions) C++14
55 / 100
 3295 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 = 200200;
const int MAXQ = 25010;
const int SQ = 510;
 
int dp[MAXN][SQ + 1];
int rez[MAXQ][SQ + 1];
int rezup[SQ + 1][MAXQ];
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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11812 KB Output is correct
2 Correct 13 ms 11960 KB Output is correct
3 Correct 13 ms 12140 KB Output is correct
4 Correct 15 ms 12324 KB Output is correct
5 Correct 24 ms 13092 KB Output is correct
6 Correct 28 ms 14628 KB Output is correct
7 Correct 28 ms 15648 KB Output is correct
8 Correct 42 ms 16948 KB Output is correct
9 Correct 99 ms 24036 KB Output is correct
10 Correct 100 ms 34336 KB Output is correct
11 Correct 149 ms 43936 KB Output is correct
12 Correct 232 ms 55152 KB Output is correct
13 Correct 238 ms 62260 KB Output is correct
14 Correct 280 ms 74272 KB Output is correct
15 Correct 328 ms 98232 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 131072 KB Output is correct
2 Correct 1522 ms 131072 KB Output is correct
3 Correct 1674 ms 131072 KB Output is correct
4 Correct 529 ms 131072 KB Output is correct
5 Correct 454 ms 131072 KB Output is correct
6 Correct 1169 ms 131072 KB Output is correct
7 Correct 2799 ms 131072 KB Output is correct
8 Correct 2450 ms 131072 KB Output is correct
9 Execution timed out 3116 ms 131072 KB Time limit exceeded (wall clock)
10 Runtime error 1879 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 2810 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2771 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Execution timed out 3295 ms 131072 KB Time limit exceeded (wall clock)
14 Runtime error 2808 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 2622 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2739 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 2605 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)