Submission #497952

#	Time	Username	Problem	Language	Result	Execution time	Memory
497952		ryangohca	스파이 (JOI13_spy)	C++17	100 / 100	242 ms	11372 KiB

spy

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// We are dancing on fire ~~  ~ Seunghee, Dun Dun Dance
using namespace std;
const int N = 2002;
int fw[N+1];
void _update(int x, int v) {
    for (; x<=N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
void update(int x, int y, int v){
    _update(x, v);
    _update(y+1, -v);
}
vector<int> tree1[2002], tree2[2002], project[2002];
int pre[2002], po[2002];
int ctr = 1;
void dfs(int x){
    if (x == 0) {dfs(tree1[0][0]); return;}
    pre[x] = ctr++;
    for (auto i : tree1[x]) dfs(i);
    po[x] = ctr - 1;
}
int ans[2002];
void dfs2(int x){
    if (x == 0) {dfs2(tree2[0][0]); return;}
    for (auto i : project[x]) update(pre[i], po[i], 1);
    ans[x] = sum(pre[x]);
    for (auto i : tree2[x]) dfs2(i);
    for (auto i : project[x]) update(pre[i], po[i], -1);
}
main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        tree1[x].push_back(i);
        tree2[y].push_back(i);
    }
    dfs(0);
    for (int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        project[b].push_back(a);
    }
    dfs2(0);
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

spy.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

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