Submission #449497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
449497	2021-08-02T06:42:49 Z	ritul_kr_singh	Traffic (CEOI11_tra)	C++17	100 / 100	1122 ms	53024 KB

#include <bits/stdc++.h>
using namespace std;
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 3e5+1;

int n, m, A, id[LIM], L[LIM], R[LIM], pre[LIM], st[LIM], stP, c;
vector<int> g[LIM], h[LIM];
array<int, 3> p[LIM];
bool vis[LIM];

void dfs0(int u){
	vis[u] = 1;
	for(int &v : g[u]) if(!vis[v]) dfs0(v);
	st[stP++] = u;
}

void dfs1(int u){
	id[u] = c + 1;
	for(int &v : h[u]) if(!id[v]) dfs1(v);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> A >> c;

	fill(L, L+n+1, n+1);

	for(int i=0; i<n; ++i){
		auto &[x, y, j] = p[i];
		cin >> x >> y;
		j = i;
	}

	for(int i=0; i<m; ++i){
		int u, v, w;
		cin >> u >> v >> w; --u, --v;
		while(w--){
			g[u].push_back(v);
			h[v].push_back(u);
			swap(u, v);
		}
	}

	for(int u=0; u<n; ++u) if(!vis[u] && !p[u][0]) dfs0(u);

	sort(p, p+n, [&](auto &x, auto &y){
		return x[1] < y[1];
	});
	
	for(int i=0; i<n; ++i){
		auto &[x, y, j] = p[i];
		if(x == A) L[j+1] = R[j+1] = i+1;
	}

	for(int i=stP; --i>=0; )
		if(!id[st[i]]) dfs1(c = st[i]);

	for(int i=0; i<stP; ++i){
		int u = st[i];
		L[id[u]] = min(L[id[u]], L[u+1]);
		R[id[u]] = max(R[id[u]], R[u+1]);
		for(int &v : g[u]){
			L[id[u]] = min(L[id[u]], L[id[v]]);
			R[id[u]] = max(R[id[u]], R[id[v]]);
		}
	}

	for(int i=0; i<n; ++i)
		pre[i+1] = pre[i] + (vis[p[i][2]] && p[i][0] == A);

	for(int i=n; --i>=0; ){
		int j = id[p[i][2]];
		if(!p[i][0])
			cout << (R[j] ? pre[R[j]] - pre[L[j]-1] : 0) nl;
	}
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	10 ms	14352 KB	Output is correct
3	Correct	9 ms	14452 KB	Output is correct
4	Correct	9 ms	14420 KB	Output is correct
5	Correct	9 ms	14352 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14412 KB	Output is correct
3	Correct	9 ms	14416 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14412 KB	Output is correct
3	Correct	9 ms	14412 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	14596 KB	Output is correct
2	Correct	13 ms	14940 KB	Output is correct
3	Correct	13 ms	14796 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	16616 KB	Output is correct
2	Correct	59 ms	19780 KB	Output is correct
3	Correct	40 ms	17488 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	19180 KB	Output is correct
2	Correct	92 ms	21208 KB	Output is correct
3	Correct	60 ms	19928 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	22228 KB	Output is correct
2	Correct	138 ms	25680 KB	Output is correct
3	Correct	222 ms	25020 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	24080 KB	Output is correct
2	Correct	166 ms	24796 KB	Output is correct
3	Correct	235 ms	25608 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	251 ms	28992 KB	Output is correct
2	Correct	259 ms	32336 KB	Output is correct
3	Correct	568 ms	33652 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	396 ms	36804 KB	Output is correct
2	Correct	464 ms	41876 KB	Output is correct
3	Correct	544 ms	35696 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	996 ms	48600 KB	Output is correct
2	Correct	519 ms	42444 KB	Output is correct
3	Correct	992 ms	44348 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	230 ms	30136 KB	Output is correct
2	Correct	595 ms	47468 KB	Output is correct
3	Correct	854 ms	42904 KB	Output is correct
4	Correct	1122 ms	53024 KB	Output is correct

Submission #449497

Compilation message