Submission #652203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
652203	2022-10-21T16:57:42 Z	DP_196	스파이 (JOI13_spy)	C++14	100 / 100	339 ms	249868 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	24788 KB	Output is correct
2	Correct	19 ms	24788 KB	Output is correct
3	Correct	18 ms	24728 KB	Output is correct
4	Correct	18 ms	24788 KB	Output is correct
5	Correct	18 ms	24812 KB	Output is correct
6	Correct	19 ms	24768 KB	Output is correct
7	Correct	18 ms	24792 KB	Output is correct
8	Correct	18 ms	24788 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	171 ms	245124 KB	Output is correct
2	Correct	167 ms	245360 KB	Output is correct
3	Correct	171 ms	244940 KB	Output is correct
4	Correct	165 ms	244964 KB	Output is correct
5	Correct	170 ms	245064 KB	Output is correct
6	Correct	167 ms	245080 KB	Output is correct
7	Correct	172 ms	245172 KB	Output is correct
8	Correct	168 ms	245056 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	249676 KB	Output is correct
2	Correct	242 ms	249612 KB	Output is correct
3	Correct	291 ms	249548 KB	Output is correct
4	Correct	276 ms	249868 KB	Output is correct
5	Correct	310 ms	249544 KB	Output is correct
6	Correct	234 ms	249004 KB	Output is correct
7	Correct	339 ms	249688 KB	Output is correct
8	Correct	314 ms	249700 KB	Output is correct