제출 #1045516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045516		juicy	스파이 (JOI13_spy)	C++17	100 / 100	57 ms	21032 KiB

spy

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e3 + 5;

int n, m;
int tin[2][N], tout[2][N], pf[N][N];
vector<int> g[2][N];

void dfs(int u, int *tin, int *tout, vector<int> *g, int &timer) {
    tin[u] = ++timer;
    for (int v : g[u]) {
        dfs(v, tin, tout, g, timer);
    }
    tout[u] = timer;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m;
    array<int, 2> root{};
    for (int i = 1; i <= n; ++i) {
        array<int, 2> p; cin >> p[0] >> p[1];
        for (auto it : {0, 1}) {
            if (p[it] == 0) {
                root[it] = i;
            } else {
                g[it][p[it]].push_back(i);
            }
        }
    }
    for (auto it : {0, 1}) {
        int _ = 0;
        dfs(root[it], tin[it], tout[it], g[it], _);
    }
    auto upd = [&](int a, int b, int x, int y) {
        ++pf[a][b];
        ++pf[x + 1][y + 1];
        --pf[x + 1][b];
        --pf[a][y + 1];
    };
    while (m--) {
        int a, b; cin >> a >> b;
        upd(tin[0][a], tin[1][b], tout[0][a], tout[1][b]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            pf[i][j] += pf[i - 1][j] + pf[i][j - 1] - pf[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << pf[tin[0][i]][tin[1][i]] << "\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70