Submission #550207

#	Time	Username	Problem	Language	Result	Execution time	Memory
550207		blue	Traffic (CEOI11_tra)	C++17	100 / 100	1016 ms	82352 KiB

tra

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
#define sz(x) int(x.size())

const int mx = 300'000;

int n, m;
int A, B;

vi edge[1+mx];
vi rev[1+mx];

vi x(1+mx), y(1+mx);

void add_edge(int u, int v)
{
	edge[u].push_back(v);
	rev[v].push_back(u);
}

vi visit;

vi exit_order;


int scc_count = 0;
vi scc(1+mx, 0);
vi scc_list[1+mx];


void dfs(int u)
{
	visit[u] = 1;
	for(int v : edge[u])
	{
		if(visit[v]) continue;
		dfs(v);
	}
	exit_order.push_back(u);
}

void dfs2(int u)
{
	scc[u] = scc_count;
	scc_list[scc[u]].push_back(u);

	for(int v : rev[u])
	{
		if(scc[v]) continue;
		dfs2(v);
	}
}



vi reachable(1+mx, 0);

void dfs3(int u)
{
	reachable[u] = 1;
	for(int v : edge[u])
	{
		if(reachable[v]) continue;
		dfs3(v);
	}
}

vi lo(1+mx, 1'000'000'000), hi(1+mx, -1);




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> A >> B;

	vi west, east;

	for(int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];

		if(x[i] == 0)
			west.push_back(i);

		if(x[i] == A)
			east.push_back(i);
	}

	for(int j = 1; j <= m; j++)
	{
		int c, d, k;
		cin >> c >> d >> k;

		add_edge(c, d);
		if(k == 2)
			add_edge(d, c);
	}



	visit = vi(1+n, 0);

	for(int i = 1; i <= n; i++)
	{
		if(visit[i]) continue;
		dfs(i);
	}

	reverse(exit_order.begin(), exit_order.end());

	for(int u : exit_order)
	{
		if(scc[u]) continue;
		scc_count++;
		dfs2(u);
	}


	for(int u : west)
	{
		if(reachable[u]) continue;
		dfs3(u);
	}


	vi goodeast;
	for(int u : east)
	{
		if(reachable[u])
			goodeast.push_back(u);
	}

	sort(goodeast.begin(), goodeast.end(), [] (int u, int v)
	{
		return y[u] < y[v];
	});

	vi geindex(1+mx);
	for(int z = 0; z < sz(goodeast); z++)
		geindex[goodeast[z]] = z;

	for(int u : goodeast)
	{
		lo[scc[u]] = min(lo[scc[u]], geindex[u]);
		hi[scc[u]] = max(hi[scc[u]], geindex[u]);
	}


	for(int s = scc_count; s >= 1; s--)
	{
		for(int u : scc_list[s])
		{
			for(int v : edge[u])
			{
				lo[s] = min(lo[s], lo[scc[v]]);
				hi[s] = max(hi[s], hi[scc[v]]);
			}
		}
	}

	sort(west.begin(), west.end(), [] (int u, int v)
	{
		return y[u] > y[v];
	});

	for(int w : west)
	{
		cout << max(0, hi[scc[w]] - lo[scc[w]] + 1) << '\n';
	}

}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9