oj.uz

Submission #147345

# Submission time Handle Problem Language Result Execution time Memory
147345 2019-08-29T02:56:31 Z gs18115 스파이 (JOI13_spy) C++14
100 / 100
 194 ms 21112 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 4 ms 1404 KB Output is correct
4 Correct 3 ms 1400 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 4 ms 1400 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 2 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16504 KB Output is correct
2 Correct 30 ms 16376 KB Output is correct
3 Correct 31 ms 16248 KB Output is correct
4 Correct 30 ms 16248 KB Output is correct
5 Correct 31 ms 16384 KB Output is correct
6 Correct 31 ms 16376 KB Output is correct
7 Correct 31 ms 16476 KB Output is correct
8 Correct 30 ms 16376 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 20844 KB Output is correct
2 Correct 124 ms 20700 KB Output is correct
3 Correct 137 ms 20612 KB Output is correct
4 Correct 143 ms 21112 KB Output is correct
5 Correct 162 ms 20724 KB Output is correct
6 Correct 117 ms 20168 KB Output is correct
7 Correct 194 ms 20724 KB Output is correct
8 Correct 194 ms 20728 KB Output is correct