oj.uz

답안 #449322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
449322 2021-08-02T05:44:05 Z ritul_kr_singh Traffic (CEOI11_tra) C++17
100 / 100
 944 ms 60324 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 3e5+1;

int n, m, A, B, dfsNum[LIM], id[LIM], L[LIM], R[LIM], pre[LIM], dfsTimer, st[LIM], stP;
vector<int> g[LIM];
array<int, 3> p[LIM];
bool can[LIM];

int dfs0(int u){
	int low = dfsNum[u] = ++dfsTimer;
	st[stP++] = u;
	for(int &v : g[u])
		if(id[v] < 0) low = min(low, dfsNum[v] ? : dfs0(v));
	if(low == dfsNum[u]){
		for(int c=n; c!=u; ){
			id[c = st[--stP]] = u;
			for(int &v : g[c]){
				L[u] = min(L[u], L[id[v] < 0 || id[v] == u ? v : id[v]]);
				R[u] = max(R[u], R[id[v] < 0 || id[v] == u ? v : id[v]]);
			}
		}
	}
	return low;
}


void dfs1(int u){
	can[u] = 1;
	for(int &v : g[u])
		if(!can[v]) dfs1(v);
}

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

	fill(L, L+n, 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;
		g[u].push_back(v);
		if(w > 1) g[v].push_back(u);
	}

	for(int u=0; u<n; ++u)
		if(!p[u][0] && !can[u]) dfs1(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 && can[j]){
			L[j] = R[j] = i+1;
			++pre[i+1];
		}
		pre[i+1] += pre[i];
	}

	fill(id, id+n, -1);
	for(int u=0; u<n; ++u)
		if(!dfsNum[u]) dfs0(u);

	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 5 ms 7324 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 7 ms 7376 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7376 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7388 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7520 KB Output is correct
2 Correct 10 ms 7756 KB Output is correct
3 Correct 8 ms 7628 KB Output is correct

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9436 KB Output is correct
2 Correct 64 ms 12308 KB Output is correct
3 Correct 30 ms 9616 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 11092 KB Output is correct
2 Correct 65 ms 13412 KB Output is correct
3 Correct 44 ms 11704 KB Output is correct

Subtask #7
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 14724 KB Output is correct
2 Correct 120 ms 18396 KB Output is correct
3 Correct 161 ms 18308 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 16840 KB Output is correct
2 Correct 122 ms 17616 KB Output is correct
3 Correct 205 ms 18792 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 22688 KB Output is correct
2 Correct 272 ms 26956 KB Output is correct
3 Correct 451 ms 28616 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 31784 KB Output is correct
2 Correct 432 ms 36744 KB Output is correct
3 Correct 385 ms 30104 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 809 ms 43592 KB Output is correct
2 Correct 462 ms 37588 KB Output is correct
3 Correct 713 ms 43824 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 27100 KB Output is correct
2 Correct 462 ms 45552 KB Output is correct
3 Correct 595 ms 39492 KB Output is correct
4 Correct 944 ms 60324 KB Output is correct