oj.uz

답안 #652202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652202 2022-10-21T16:53:04 Z DP_196 스파이 (JOI13_spy) C++14
10 / 100
 377 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define builtin_popcount __builtin_popcountll

#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

const int N = (int)1e5 + 5;
const int Sz = (int)5e5 + 2;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
/***------------------------- END ---------------------------***/
int n, m, r1, r2, res[2005];
vector<int> adj[2005], g[2005];
bitset<Sz> bit1[2005], bit2[2005];

void dfs1(int u) {
	for (auto v : adj[u]) {
		bit1[v] |= bit1[u];
		dfs1(v);
	}
}

void dfs2(int u) {
	res[u] = (bit1[u] & bit2[u]).count();
	for (auto v : g[u]) {
		bit2[v] |= bit2[u];
		dfs2(v);
	}
}

#define TASK ""
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		
		if (!u) r1 = i; else adj[u].push_back(i);
		if (!v) r2 = i; else g[v].push_back(i);
	}
	
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		bit1[x][i] = bit2[y][i] = 1;
	}
	
	dfs1(r1);
	dfs2(r2);
	
	for (int i = 1; i <= n; i++) cout << res[i] << '\n';
	
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 37004 KB Output is correct
2 Correct 27 ms 37008 KB Output is correct
3 Correct 23 ms 24864 KB Output is correct
4 Correct 22 ms 24808 KB Output is correct
5 Correct 23 ms 25684 KB Output is correct
6 Correct 22 ms 25684 KB Output is correct
7 Correct 24 ms 29988 KB Output is correct
8 Correct 21 ms 26192 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 377 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -