Submission #1021834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021834		MilosMilutinovic	스파이 (JOI13_spy)	C++14	100 / 100	254 ms	8720 KiB

spy

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70