oj.uz

답안 #449497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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