oj.uz

Submission #497952

# Submission time Handle Problem Language Result Execution time Memory
497952 2021-12-24T06:00:53 Z ryangohca 스파이 (JOI13_spy) C++17
100 / 100
 242 ms 11372 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 1 ms 444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 720 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 3 ms 592 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11372 KB Output is correct
2 Correct 219 ms 10040 KB Output is correct
3 Correct 222 ms 10292 KB Output is correct
4 Correct 242 ms 10448 KB Output is correct
5 Correct 226 ms 10972 KB Output is correct
6 Correct 215 ms 9652 KB Output is correct
7 Correct 239 ms 11296 KB Output is correct
8 Correct 239 ms 11240 KB Output is correct