oj.uz

Submission #76113

# Submission time Handle Problem Language Result Execution time Memory
76113 2018-09-12T06:39:47 Z cubecube1000 스파이 (JOI13_spy) C++14
100 / 100
 576 ms 83388 KB 
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const ll MAX=2005;
const ll INFint=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
int par[2][MAX],cnt[MAX][MAX],sum[MAX][MAX],p1,p2,sum2[MAX][MAX],n,m;
vector<int> conn[2][MAX];
void calc(int x1,int x2,int r){
    r+=cnt[x1][x2];
    sum[x1][x2]=r;
    for(int i=0;i<conn[1][x2].size();i++) calc(x1,conn[1][x2][i],r);
    return;
}
void calc2(int x1,int x2,int r){
    r+=sum[x1][x2];
    sum2[x1][x2]=r;
    for(int i=0;i<conn[0][x1].size();i++) calc2(conn[0][x1][i],x2,r);
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&par[0][i],&par[1][i]);
        conn[0][par[0][i]].push_back(i),conn[1][par[1][i]].push_back(i);
        if(par[0][i]==0) p1=i;
        if(par[1][i]==0) p2=i;
    }
    for(int i=0;i<m;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        cnt[t1][t2]++;
    }
    for(int i=1;i<=n;i++) calc(i,p2,0);
    for(int i=1;i<=n;i++) calc2(p1,i,0);
    for(int i=1;i<=n;i++){
        printf("%d\n",sum2[i][i]);
    }
}

Compilation message

spy.cpp: In function 'void calc(int, int, int)':
spy.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<conn[1][x2].size();i++) calc(x1,conn[1][x2][i],r);
                 ~^~~~~~~~~~~~~~~~~~~
spy.cpp: In function 'void calc2(int, int, int)':
spy.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<conn[0][x1].size();i++) calc2(conn[0][x1][i],x2,r);
                 ~^~~~~~~~~~~~~~~~~~~
spy.cpp: In function 'int main()':
spy.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
spy.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&par[0][i],&par[1][i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
spy.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2936 KB Output is correct
4 Correct 4 ms 2936 KB Output is correct
5 Correct 5 ms 3060 KB Output is correct
6 Correct 4 ms 3060 KB Output is correct
7 Correct 6 ms 3256 KB Output is correct
8 Correct 5 ms 3428 KB Output is correct
9 Correct 2 ms 3428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 38460 KB Output is correct
2 Correct 324 ms 38460 KB Output is correct
3 Correct 196 ms 38460 KB Output is correct
4 Correct 193 ms 38460 KB Output is correct
5 Correct 236 ms 38460 KB Output is correct
6 Correct 236 ms 38460 KB Output is correct
7 Correct 300 ms 39016 KB Output is correct
8 Correct 261 ms 39144 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 53028 KB Output is correct
2 Correct 422 ms 53028 KB Output is correct
3 Correct 307 ms 57780 KB Output is correct
4 Correct 317 ms 66236 KB Output is correct
5 Correct 384 ms 70712 KB Output is correct
6 Correct 351 ms 70712 KB Output is correct
7 Correct 527 ms 79028 KB Output is correct
8 Correct 576 ms 83388 KB Output is correct