Submission #704140

#	Time	Username	Problem	Language	Result	Execution time	Memory
704140		karrigan	스파이 (JOI13_spy)	C++14	0 / 100	133 ms	20752 KiB

spy

#include<bits/stdc++.h>
using namespace std;
int tme=0;
int in[2009];
int out[2009];
vector<int>a[2009];
vector<int>b[2009];
int num[2009][2009];
int p[2009];
bool cmp(int i,int j){
return in[i]<in[j];
}
void dfs2(int u,int par){
in[u]=++tme;
p[u]=par;
for (auto v:b[u])dfs2(v,u);
out[u]=tme;
}
vector<int>id;
void dfs(int u){
for (auto v:a[u]){
    for (auto v1:id){
        num[v][v1]+=num[v][p[v1]];
    }
    for (auto v1:id){
        num[v][v1]+=num[u][v1];
    }
    dfs(v);
}
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int r1=0,r2=0;
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        id.push_back(i);
        int x,y;
        cin>>x>>y;
        if (x==0)r1=i;
        else a[x].push_back(i);
        if (y==0)r2=i;
        else b[y].push_back(i);
    }
    dfs2(r2,0);
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        num[x][y]++;
    }
    sort(id.begin(),id.end(),cmp);
    dfs(r1);
    for (int i=1;i<=n;i++){
        cout<<num[i][i]<<'\n';
    }
}

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