oj.uz

Submission #55003

# Submission time Handle Problem Language Result Execution time Memory
55003 2018-07-05T19:14:27 Z dfistric Regions (IOI09_regions) C++14
55 / 100
 3325 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 + 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);
 
 // clock_t tata = clock();
 
  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 << rezup[a][b] << " ";
      cout << rez[a][b] << "\n";
    } else if (a < SQ) {
      cout << rezup[a][b] << "\n";
    } 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 << "\n";
    }
  }
 
 // cout << fixed << (double) (clock() - tata) << "\n";
 
  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:98: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:99: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 14 ms 12536 KB Output is correct
2 Correct 13 ms 12724 KB Output is correct
3 Correct 15 ms 12804 KB Output is correct
4 Correct 16 ms 13108 KB Output is correct
5 Correct 23 ms 13900 KB Output is correct
6 Correct 31 ms 15472 KB Output is correct
7 Correct 28 ms 16444 KB Output is correct
8 Correct 49 ms 17724 KB Output is correct
9 Correct 73 ms 24636 KB Output is correct
10 Correct 111 ms 35060 KB Output is correct
11 Correct 145 ms 44604 KB Output is correct
12 Correct 238 ms 55860 KB Output is correct
13 Correct 280 ms 63036 KB Output is correct
14 Correct 276 ms 75068 KB Output is correct
15 Correct 341 ms 98876 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 131072 KB Output is correct
2 Correct 1219 ms 131072 KB Output is correct
3 Correct 1692 ms 131072 KB Output is correct
4 Correct 545 ms 131072 KB Output is correct
5 Correct 604 ms 131072 KB Output is correct
6 Correct 881 ms 131072 KB Output is correct
7 Correct 1834 ms 131072 KB Output is correct
8 Correct 1912 ms 131072 KB Output is correct
9 Execution timed out 3325 ms 131072 KB Time limit exceeded (wall clock)
10 Runtime error 1851 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 2750 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 2447 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3195 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 2744 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 2314 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2306 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 2083 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)