oj.uz

Submission #1021834

# Submission time Handle Problem Language Result Execution time Memory
1021834 2024-07-13T05:57:05 Z MilosMilutinovic 스파이 (JOI13_spy) C++14
100 / 100
 254 ms 8720 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> pr(n, vector<int>(2));
  for (int i = 0; i < n; i++) { 
    cin >> pr[i][0] >> pr[i][1];
    --pr[i][0]; --pr[i][1];
  }
  int ra, rb;
  vector<vector<vector<int>>> g(n, vector<vector<int>>(2));
  for (int i = 0; i < n; i++) {
    if (pr[i][0] == -1) {
      ra = i;
    } else {
      g[pr[i][0]][0].push_back(i);
    }
    if (pr[i][1] == -1) {
      rb = i;
    } else {
      g[pr[i][1]][1].push_back(i);
    }
  }
  vector<vector<int>> tin(n, vector<int>(2));
  vector<vector<int>> tout(n, vector<int>(2));
  int T = 0;
  function<void(int, int)> Dfs = [&](int v, int t) {
    tin[v][t] = ++T;
    for (int u : g[v][t]) {
      Dfs(u, t);
    }
    tout[v][t] = ++T;
  };
  Dfs(ra, 0);
  Dfs(rb, 1);
  vector<vector<int>> qs(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    qs[y].push_back(x);
  }
  vector<int> res(n);
  for (int v = 0; v < n; v++) {
    vector<int> cnt(n);
    for (int u : qs[v]) {
      cnt[u] += 1;
    }
    function<void(int)> Push = [&](int v) {
      for (int u : g[v][0]) {
        cnt[u] += cnt[v];
        Push(u);
      }
    };
    Push(ra);
    function<void(int)> Go = [&](int v) {
      res[v] += cnt[v];
      for (int u : g[v][1]) {
        Go(u);
      }
    };
    Go(v);
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

Compilation message

spy.cpp: In function 'int main()':
spy.cpp:40:6: warning: 'rb' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |   Dfs(rb, 1);
      |   ~~~^~~~~~~
spy.cpp:15:7: warning: 'ra' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |   int ra, rb;
      |       ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1372 KB Output is correct
2 Correct 140 ms 1372 KB Output is correct
3 Correct 20 ms 856 KB Output is correct
4 Correct 20 ms 856 KB Output is correct
5 Correct 55 ms 1116 KB Output is correct
6 Correct 72 ms 1132 KB Output is correct
7 Correct 95 ms 1112 KB Output is correct
8 Correct 63 ms 1116 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 8720 KB Output is correct
2 Correct 190 ms 7868 KB Output is correct
3 Correct 70 ms 7912 KB Output is correct
4 Correct 72 ms 8132 KB Output is correct
5 Correct 106 ms 8284 KB Output is correct
6 Correct 110 ms 7104 KB Output is correct
7 Correct 175 ms 8596 KB Output is correct
8 Correct 116 ms 8604 KB Output is correct