Submission #391905

#	Time	Username	Problem	Language	Result	Execution time	Memory
391905		wind_reaper	Traffic (CEOI11_tra)	C++17	0 / 100	613 ms	56720 KiB

tra

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9