oj.uz

Submission #42969

# Submission time Handle Problem Language Result Execution time Memory
42969 2018-03-07T08:41:02 Z smu201111192 스파이 (JOI13_spy) C++14
100 / 100
 323 ms 62856 KB 
#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 2005;
int par1[MAXN],par2[MAXN];
vector<int> tree1[MAXN],tree2[MAXN];
int cnt[MAXN][MAXN];
int pcnt[MAXN][MAXN]; //[노드,path]
void dfs(int here,int dad,vector<int> tree[MAXN],int par[MAXN]){
    par[here] = dad;
    for(auto x:tree[here]){
        if(x == dad) continue;
        dfs(x,here,tree,par);
    }
}
vector<int> g(int here,int par[MAXN]){
    vector<int> ret;
    while(here != 0){
        ret.push_back(here);
        here = par[here];
    }
    return ret;
}
int tot = 0;
void dfs2(int here,int root,int dad,vector<int> tree[MAXN]){
    pcnt[root][here] = tot;
    for(int i=0;i<tree[here].size();i++){
        int there = tree[here][i];
        if(there == dad) continue;
        tot += cnt[root][there];
        dfs2(there,root,here,tree);
        tot -= cnt[root][there];
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m; cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int u,v; cin>>u>>v;
        tree1[u].push_back(i);
        tree2[v].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        cnt[a][b]++;
    }
    dfs(0,-1,tree1,par1);
    dfs(0,-1,tree2,par2);
    
    for(int i=1;i<=n;i++){
        tot = 0;
        dfs2(0,i,-1,tree2);
    }
    for(int i=1;i<=n;i++){
        vector<int> L = g(i,par1);
        vector<int> R = g(i,par2);
        int ans = 0;
        for(auto x:L){
            ans += pcnt[x][i];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message

spy.cpp: In function 'void dfs2(int, int, int, std::vector<int>*)':
spy.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[here].size();i++){
                  ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 22748 KB Output is correct
2 Correct 215 ms 22748 KB Output is correct
3 Correct 58 ms 22748 KB Output is correct
4 Correct 55 ms 22748 KB Output is correct
5 Correct 87 ms 22748 KB Output is correct
6 Correct 90 ms 22748 KB Output is correct
7 Correct 139 ms 22912 KB Output is correct
8 Correct 99 ms 22912 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 32524 KB Output is correct
2 Correct 273 ms 32524 KB Output is correct
3 Correct 143 ms 37272 KB Output is correct
4 Correct 146 ms 45608 KB Output is correct
5 Correct 221 ms 50056 KB Output is correct
6 Correct 162 ms 50056 KB Output is correct
7 Correct 289 ms 58584 KB Output is correct
8 Correct 255 ms 62856 KB Output is correct