oj.uz

Submission #704143

# Submission time Handle Problem Language Result Execution time Memory
704143 2023-03-01T17:18:15 Z karrigan 스파이 (JOI13_spy) C++14
0 / 100
 121 ms 32156 KB 
#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 dp[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){
        dp[v][v1]+=dp[v][p[v1]]+num[v][v1];
    }
    for (auto v1:id){
        dp[v][v1]+=dp[u][v1];
        dp[v][v1]-=dp[u][p[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<<dp[i][i]<<'\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 22508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 32156 KB Output isn't correct
2 Halted 0 ms 0 KB -