oj.uz

Submission #1045516

# Submission time Handle Problem Language Result Execution time Memory
1045516 2024-08-06T04:47:47 Z juicy 스파이 (JOI13_spy) C++17
100 / 100
 57 ms 21032 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 0 ms 2652 KB Output is correct
8 Correct 0 ms 2604 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 6 ms 16476 KB Output is correct
2 Correct 6 ms 16476 KB Output is correct
3 Correct 8 ms 16216 KB Output is correct
4 Correct 5 ms 16216 KB Output is correct
5 Correct 6 ms 16284 KB Output is correct
6 Correct 6 ms 16220 KB Output is correct
7 Correct 6 ms 16476 KB Output is correct
8 Correct 6 ms 16220 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20756 KB Output is correct
2 Correct 43 ms 20816 KB Output is correct
3 Correct 45 ms 20704 KB Output is correct
4 Correct 47 ms 21032 KB Output is correct
5 Correct 57 ms 20656 KB Output is correct
6 Correct 41 ms 20052 KB Output is correct
7 Correct 53 ms 20632 KB Output is correct
8 Correct 51 ms 20564 KB Output is correct