oj.uz

답안 #391905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391905 2021-04-20T05:58:38 Z wind_reaper Traffic (CEOI11_tra) C++17
0 / 100
 613 ms 56720 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 500001;

vector<int> g[MXN];
vector<vector<int>> scc;

int comp[MXN], tin[MXN], low[MXN], idx[MXN];
vector<bool> onstk(MXN);
int cur = 0, timer = 0;

vector<int> st;

void tarjan(int node){
	tin[node] = low[node] = timer++;
	st.push_back(node);
	onstk[node] = 1;

	for(int v : g[node]){
		if(tin[v] == -1){
			tarjan(v);
			low[node] = min(low[v], low[node]);
		}
		else if(onstk[v]){
			low[node] = min(low[node], tin[v]);
		}
	}

	if(tin[node] == low[node]){
		while(1){
			int v = st.back();
			st.pop_back();
			onstk[v] = 0;
			comp[v] = cur;
			if(node == v)
				break;
		}
		cur++;
	}
}

int sz[MXN];
vector<bool> vis;
vector<int> ord;

void dfs(int node){
	vis[node] = 1;
	for(int v : scc[node]){
		if(!vis[v]){
			dfs(v);
		}
	}
	ord.push_back(node);
}

void dfs2(int node){
	vis[node] = 1;

	for(int v : scc[node]){
		if(!vis[v]){
			dfs2(v);
			sz[node] += sz[v];
		}
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n, m, a, b;
	cin >> n >> m >> a >> b;

	vector<array<int, 2>> points(n);
	vector<array<int, 2>> edge;

	for(auto& [x, y] : points)
		cin >> x >> y;

	for(int i = 0; i < m; i++){
		int u, v, k;
		cin >> u >> v >> k;
		--u, --v;
		g[u].push_back(v);
		edge.push_back({u, v});
		if(k == 2){
			g[v].push_back(u);
			edge.push_back({v, u});
		}
	}

	memset(tin, -1, sizeof tin);
	memset(low, -1, sizeof low);

	for(int i = 0; i < n; i++)
		if(tin[i] == -1)
			tarjan(i);

	vector<array<int, 2>> west;

	for(int i = 0; i < n; i++){
		if(points[i][0] == a) sz[comp[i]]++;
		if(points[i][0] == 0) west.push_back({-points[i][1], i});
	}

	scc.resize(cur);
	vis.resize(cur);

	for(auto& [u, v] : edge){
		u = comp[u], v = comp[v];
		if(u == v)
			continue;
		scc[u].push_back(v);
	}

	for(int i = 0; i < cur; i++){
		if(!vis[i])
			dfs(i);
	}

	reverse(ord.begin(), ord.end());
	fill(vis.begin(), vis.end(), 0);

	for(int v : ord)
		if(!vis[v])
			dfs2(v);

	sort(west.begin(), west.end());
	
	int K = west.size();
	for(int i = 0; i < K; i++){
		cout << sz[comp[west[i][1]]] << endl;
	}

	return 0; 
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Correct 10 ms 15948 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Incorrect 10 ms 15968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16000 KB Output is correct
2 Incorrect 10 ms 15948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 16376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 18972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 21064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 26548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 27272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 191 ms 35716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 334 ms 48836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 613 ms 56720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 210 ms 43540 KB Output isn't correct
2 Halted 0 ms 0 KB -