Submission #147345

#	Time	Username	Problem	Language	Result	Execution time	Memory
147345		gs18115	스파이 (JOI13_spy)	C++14	100 / 100	194 ms	21112 KiB

spy

#include<iostream>
#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
vector<int>adj1[2010],adj2[2010];
int in1[2010],out1[2010];
int nct1=1;
int in2[2010],out2[2010];
int nct2=1;
void dfs1(int x)
{
    in1[x]=nct1++;
    for(int t:adj1[x])
        dfs1(t);
    out1[x]=nct1;
    return;
}
void dfs2(int x)
{
    in2[x]=nct2++;
    for(int t:adj2[x])
        dfs2(t);
    out2[x]=nct2;
    return;
}
int n,q,i;
int b1,b2;
int S[2010][2010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(i=0;i<n;i++)
    {
        int p,q;
        cin>>p>>q;
        if(p==0)
            b1=i;
        else
            adj1[p-1].eb(i);
        if(q==0)
            b2=i;
        else
            adj2[q-1].eb(i);
    }
    dfs1(b1);
    dfs2(b2);
    for(i=0;i<q;i++)
    {
        int r,s;
        cin>>r>>s;
        int si=in1[--r];
        int ti=out1[r];
        int sj=in2[--s];
        int tj=out2[s];
        S[si][sj]++;
        S[si][tj]--;
        S[ti][sj]--;
        S[ti][tj]++;
    }
    for(i=1;i<n+3;i++)
        for(int j=1;j<n+3;j++)
            S[i][j]+=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
    for(i=0;i<n;i++)
        cout<<S[in1[i]][in2[i]]<<'\n';
    return 0;
}

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