Submission #652203

#	Time	Username	Problem	Language	Result	Execution time	Memory
652203		DP_196	스파이 (JOI13_spy)	C++14	100 / 100	339 ms	249868 KiB

spy

#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;
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) {
	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].set(i);
		bit2[y].set(i);
	}
	
	dfs1(r1);
	dfs2(r2);
	
	for (int i = 1; i <= n; i++) {
		cout << (bit1[i] & bit2[i]).count() << '\n';
	}
	
	return 0;
}

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