oj.uz

Submission #159678

# Submission time Handle Problem Language Result Execution time Memory
159678 2019-10-23T22:04:29 Z luciocf Traffic (CEOI11_tra) C++14
100 / 100
 791 ms 73940 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 3e5+10;
const int inf = 1e9+10;

int n, m, A, B;
int x[maxn], y[maxn];

int in[maxn], low[maxn], scc[maxn], tt, cc;

int mnScc[maxn], mxScc[maxn];

int up[maxn], down[maxn], mp[maxn];

bool mark[maxn], isEast[maxn], isWest[maxn];
bool sccEast[maxn], reach[maxn];

vector<int> grafo[maxn];
vector<int> dag[maxn], dagT[maxn], topo;

stack<int> stk;

void dfs(int u)
{
	in[u] = low[u] = ++tt;
	stk.push(u);

	for (auto v: grafo[u])
	{
		if (in[v])
		{
			low[u] = min(low[u], in[v]);
			continue;
		}

		dfs(v);

		low[u] = min(low[u], low[v]);
	}

	if (in[u] == low[u])
	{
		++cc;

		while (true)
		{
			int v = stk.top(); stk.pop();

			scc[v] = cc, in[v] = inf;

			if (isEast[v])
				sccEast[cc] = true;

			if (v == u) break;
		}
	}
}

void topsort(int u)
{
	mark[u] = true;

	for (auto v: dag[u])
		if (!mark[v])
			topsort(v);

	topo.push_back(u);
}

void getWest(void)
{
	reverse(topo.begin(), topo.end());

	for (auto u: topo)
	{
		if (sccEast[u])
			reach[u] = true;

		for (auto v: dagT[u])
			reach[u] |= reach[v];
	}

	reverse(topo.begin(), topo.end());
}

void getEast(void)
{
	for (int i = 1; i <= cc; i++)
		up[i] = 0, down[i] = inf;

	for (auto u: topo)
	{
		up[u] = max(up[u], mxScc[u]);
		down[u] = min(down[u], mnScc[u]);

		for (auto v: dag[u])
		{
			up[u] = max(up[u], up[v]);
			down[u] = min(down[u], down[v]);
		}
	}
}

int main(void)
{
	scanf("%d %d %d %d", &n, &m, &A, &B);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &x[i], &y[i]);

		if (x[i] == 0) isEast[i] = true;
		if (x[i] == A) isWest[i] = true;
	}

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		if (w == 1)
			grafo[u].push_back(v);
		else
		{
			grafo[u].push_back(v);
			grafo[v].push_back(u);
		}
	}

	for (int i = 1; i <= n; i++)
		if (!in[i])
			dfs(i);

	for (int i = 1; i <= n; i++)
	{
		for (auto v: grafo[i])
		{
			if (scc[i] != scc[v])
			{
				dag[scc[i]].push_back(scc[v]);
				dagT[scc[v]].push_back(scc[i]);
			}
		}
	}

	for (int i = 1; i <= cc; i++)
		if (!mark[i])
			topsort(i);

	getWest();

	vector<pii> V;
	for (int i = 1; i <= n; i++)
		if (isWest[i])
			V.push_back({y[i], i});

	sort(V.begin(), V.end());

	int aux = 0;
	for (auto u: V)
		if (reach[scc[u.ss]])
			mp[u.ss] = ++aux;

	for (int i = 1; i <= cc; i++)
		mnScc[i] = inf, mxScc[i] = 0;

	for (int i = 1; i <= n; i++)
	{
		if (reach[scc[i]] && isWest[i])
		{
			mnScc[scc[i]] = min(mnScc[scc[i]], mp[i]);
			mxScc[scc[i]] = max(mxScc[scc[i]], mp[i]);
		}
	}

	getEast();

	V.clear();

	for (int i = 1; i <= n; i++)
		if (isEast[i])
			V.push_back({y[i], i});

	sort(V.begin(), V.end());

	for (int i = V.size()-1; i >= 0; i--)
	{
		int u = V[i].ss;

		if (!up[scc[u]]) printf("0\n");
		else printf("%d\n", up[scc[u]]-down[scc[u]]+1);
	}
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &n, &m, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21624 KB Output is correct
2 Correct 21 ms 21496 KB Output is correct
3 Correct 20 ms 21624 KB Output is correct
4 Correct 20 ms 21496 KB Output is correct
5 Correct 20 ms 21496 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21496 KB Output is correct
2 Correct 21 ms 21624 KB Output is correct
3 Correct 20 ms 21624 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21496 KB Output is correct
2 Correct 21 ms 21608 KB Output is correct
3 Correct 20 ms 21596 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21880 KB Output is correct
2 Correct 27 ms 22392 KB Output is correct
3 Correct 25 ms 22136 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 24692 KB Output is correct
2 Correct 84 ms 29256 KB Output is correct
3 Correct 59 ms 25520 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 26996 KB Output is correct
2 Correct 101 ms 30836 KB Output is correct
3 Correct 80 ms 29684 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 33008 KB Output is correct
2 Correct 160 ms 39024 KB Output is correct
3 Correct 224 ms 36032 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 32700 KB Output is correct
2 Correct 161 ms 36848 KB Output is correct
3 Correct 214 ms 36080 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 42492 KB Output is correct
2 Correct 299 ms 52712 KB Output is correct
3 Correct 427 ms 49400 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 57064 KB Output is correct
2 Correct 575 ms 68756 KB Output is correct
3 Correct 461 ms 53876 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 56416 KB Output is correct
2 Correct 534 ms 70896 KB Output is correct
3 Correct 791 ms 65748 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 51632 KB Output is correct
2 Correct 630 ms 73940 KB Output is correct
3 Correct 709 ms 65616 KB Output is correct
4 Correct 735 ms 69636 KB Output is correct