oj.uz

Submission #550207

# Submission time Handle Problem Language Result Execution time Memory
550207 2022-04-17T14:54:58 Z blue Traffic (CEOI11_tra) C++17
100 / 100
 1016 ms 82352 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 14 ms 29772 KB Output is correct
3 Correct 14 ms 29668 KB Output is correct
4 Correct 14 ms 29620 KB Output is correct
5 Correct 13 ms 29652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29652 KB Output is correct
2 Correct 17 ms 29652 KB Output is correct
3 Correct 14 ms 29644 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29656 KB Output is correct
2 Correct 15 ms 29688 KB Output is correct
3 Correct 15 ms 29652 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29908 KB Output is correct
2 Correct 20 ms 30308 KB Output is correct
3 Correct 19 ms 30080 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32224 KB Output is correct
2 Correct 61 ms 36080 KB Output is correct
3 Correct 45 ms 32804 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 34396 KB Output is correct
2 Correct 75 ms 37536 KB Output is correct
3 Correct 56 ms 35776 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39244 KB Output is correct
2 Correct 151 ms 43712 KB Output is correct
3 Correct 217 ms 42492 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 41048 KB Output is correct
2 Correct 158 ms 42856 KB Output is correct
3 Correct 226 ms 43020 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 48940 KB Output is correct
2 Correct 287 ms 54908 KB Output is correct
3 Correct 543 ms 55136 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 60804 KB Output is correct
2 Correct 474 ms 68456 KB Output is correct
3 Correct 505 ms 58056 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 72148 KB Output is correct
2 Correct 518 ms 70448 KB Output is correct
3 Correct 962 ms 71472 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 54500 KB Output is correct
2 Correct 573 ms 74052 KB Output is correct
3 Correct 798 ms 68816 KB Output is correct
4 Correct 1016 ms 82352 KB Output is correct