oj.uz

답안 #34946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34946 2017-11-17T08:42:24 Z DifferentHeaven 스파이 (JOI13_spy) C++14
100 / 100
 216 ms 6596 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 2007;
int m, n, pa, pb, A, B, u, v;
int d[N], res[N];
vector <int> adjA[N], adjB[N], q[N];

void DFS(int u, int val){
	for (int v: adjA[u]){
		d[v] += val;
		DFS(v, d[v]);
	}
}

void DFS1(int u){
	res[u] += d[u];
	for (int v: adjB[u]){
		DFS1(v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("test.inp", "r", stdin);
	// freopen("test.out", "w", stdout);
	read(n); read(m);
	for (int i = 1; i <= n; i++){
		read(pa); read(pb);
		if (pa){
			adjA[pa].push_back(i);
		}
		else 
			A = i;
		if (pb){
			adjB[pb].push_back(i);
		}
		else
			B = i;
	}
	for (int i = 1; i <= m; i++){
		read(u); read(v);
		q[v].push_back(u);
	}
	for (int i = 1; i <= n; i++){
		memset(d, 0, sizeof(d));
		for (int x: q[i]){
			d[x]++;
		}
		DFS(A, d[A]);
		// for (int j = 1; j <= n; j++)
		// 	write(d[j]);
		// putchar('\n');
		DFS1(i);
	}
	for (int i = 1; i <= n; i++)
		writeln(res[i]);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2332 KB Output is correct
2 Correct 0 ms 2332 KB Output is correct
3 Correct 0 ms 2332 KB Output is correct
4 Correct 0 ms 2332 KB Output is correct
5 Correct 0 ms 2332 KB Output is correct
6 Correct 0 ms 2332 KB Output is correct
7 Correct 0 ms 2332 KB Output is correct
8 Correct 0 ms 2332 KB Output is correct
9 Correct 0 ms 2332 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 2464 KB Output is correct
2 Correct 149 ms 2464 KB Output is correct
3 Correct 13 ms 2332 KB Output is correct
4 Correct 16 ms 2332 KB Output is correct
5 Correct 46 ms 2464 KB Output is correct
6 Correct 46 ms 2468 KB Output is correct
7 Correct 86 ms 2464 KB Output is correct
8 Correct 56 ms 2464 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 5632 KB Output is correct
2 Correct 216 ms 6596 KB Output is correct
3 Correct 83 ms 4968 KB Output is correct
4 Correct 103 ms 6344 KB Output is correct
5 Correct 106 ms 5368 KB Output is correct
6 Correct 89 ms 6556 KB Output is correct
7 Correct 126 ms 5500 KB Output is correct
8 Correct 129 ms 5500 KB Output is correct