Submission #1130663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130663		CrabCNH	스파이 (JOI13_spy)	C++20	100 / 100	262 ms	126488 KiB

spy

#include <bits/stdc++.h>

#define int   long long
#define pii   pair <int, int>
#define fi    first
#define se    second
#define szf   sizeof
#define sz(s) (int)((s).size())

using namespace std;

template<class T> void mini (T &t, T f) {if (t > f) t = f;}
template<class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int N = 4e3 + 5;
const int inf = 1e18 + 7;

int n;
int d[N][N];
vector <int> adj1[N], adj2[N];
int cur1 = 0, cur2 = 0, rt1, rt2;
int st1[N], en1[N], st2[N], en2[N];
vector <int> t1, t2;
int Lim = 0;

void dfs1 (int u, int p) {
    t1.push_back (u);
    for (auto v : adj1[u]) {
        if (v == p) {
            continue;
        }
        dfs1 (v, u);
        t1.push_back (u);
    }
}

void dfs2 (int u, int p) {
    t2.push_back (u);
    for (auto v : adj2[u]) {
        if (v == p) {
            continue;
        }
        dfs2 (v, u);
        t2.push_back (u);
    }
}

void update (int l, int r, int u, int v) {
    d[l][u] ++;
    if (r + 1 <= Lim) {
        d[r + 1][u] --;
    }
    if (v + 1 <= Lim) {
        d[l][v + 1] --;
    }
    if (r + 1 <= Lim && v + 1 <= Lim) {
        d[r + 1][v + 1] ++;
    }
}

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    #define task "crab"
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int Pa, Qa;
        cin >> Pa >> Qa;
        if (Pa == 0) {
            rt1 = i;
        } 
        else {
            adj1[i].push_back (Pa);
            adj1[Pa].push_back (i);
        }
        if (Qa == 0) {
            rt2 = i;
        }
        else {
            adj2[i].push_back (Qa);
            adj2[Qa].push_back (i);
        }
        st1[i] = en1[i] = st2[i] = en2[i] = -1;
    }
    dfs1 (rt1, 0);
    dfs2 (rt2, 0);
    for (int i = 0; i < t1.size (); i ++) {
        int cur = t1[i];
        if (st1[cur] == -1) {
            st1[cur] = i + 1;
            en1[cur] = i + 1;
        }
        else {
            en1[cur] = i + 1;
        }
    }
    for (int i = 0; i < t2.size (); i ++) {
        int cur = t2[i];
        if (st2[cur] == -1) {
            st2[cur] = i + 1;
            en2[cur] = i + 1;
        }
        else {
            en2[cur] = i + 1;
        }
    }
    Lim = t1.size () + 1;
    for (int i = 1; i <= m; i ++) {
        int Rb, Sb;
        cin >> Rb >> Sb;
        update (st1[Rb], en1[Rb], st2[Sb], en2[Sb]);
    }
    for (int i = 1; i <= Lim; i ++) {
        for (int j = 2; j <= Lim; j ++) {
            d[i][j] += d[i][j - 1];
        }
    }
    for (int i = 1; i <= Lim; i ++) {
        for (int j = 2; j <= Lim; j ++) {
            d[i][j] += d[i - 1][j];
        }
    }
    for (int i = 1; i <= n; i ++) {
        cout << d[en1[i]][en2[i]] << '\n';
    }
    return 0;
}
// Brian the Crab
// stkwa 10324

Compilation message (stderr)

spy.cpp: In function 'int main()':
spy.cpp:67:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
spy.cpp:68:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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