Submission #159678

#	Time	Username	Problem	Language	Result	Execution time	Memory
159678		luciocf	Traffic (CEOI11_tra)	C++14	100 / 100	791 ms	73940 KiB

tra

#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 (stderr)

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 / 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