oj.uz

Submission #766124

# Submission time Handle Problem Language Result Execution time Memory
766124 2023-06-25T10:30:09 Z bachhoangxuan 스파이 (JOI13_spy) C++17
100 / 100
 280 ms 249804 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 2005
#define maxa 500005
int n,m;
vector<int> edge1[maxn],edge2[maxn];
bitset<maxa> ans2[maxn],ans1[maxn];
void dfs1(int u){
    for(int v:edge1[u]){
        ans1[v]|=ans1[u];
        dfs1(v);
    }
}
void dfs2(int u){
    for(int v:edge2[u]){
        ans2[v]|=ans2[u];
        dfs2(v);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int p1,p2;cin >> p1 >> p2;
        edge1[p1].push_back(i);
        edge2[p2].push_back(i);
    }
    for(int i=0;i<m;i++){
        int p1,p2;cin >> p1 >> p2;
        ans1[p1][i]=1;ans2[p2][i]=1;
    }
    dfs1(0);dfs2(0);
    for(int i=1;i<=n;i++){
        ans1[i]&=ans2[i];
        cout << ans1[i].count() << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24916 KB Output is correct
2 Correct 17 ms 24916 KB Output is correct
3 Correct 16 ms 24784 KB Output is correct
4 Correct 17 ms 24788 KB Output is correct
5 Correct 20 ms 24808 KB Output is correct
6 Correct 17 ms 24864 KB Output is correct
7 Correct 17 ms 24788 KB Output is correct
8 Correct 17 ms 24788 KB Output is correct
9 Correct 1 ms 556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 245296 KB Output is correct
2 Correct 154 ms 245240 KB Output is correct
3 Correct 148 ms 245016 KB Output is correct
4 Correct 149 ms 245096 KB Output is correct
5 Correct 154 ms 245160 KB Output is correct
6 Correct 171 ms 245280 KB Output is correct
7 Correct 153 ms 245136 KB Output is correct
8 Correct 154 ms 245080 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 249676 KB Output is correct
2 Correct 203 ms 249548 KB Output is correct
3 Correct 244 ms 249404 KB Output is correct
4 Correct 235 ms 249804 KB Output is correct
5 Correct 265 ms 249504 KB Output is correct
6 Correct 199 ms 248936 KB Output is correct
7 Correct 280 ms 249544 KB Output is correct
8 Correct 268 ms 249516 KB Output is correct