Submission #682121

#	Time	Username	Problem	Language	Result	Execution time	Memory
682121		as111	Traffic (CEOI11_tra)	C++14	0 / 100	1192 ms	44644 KiB

tra

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

typedef pair<int, int> pi;
const int MAXN = 300000;
int N, M;


vector<int> adj[MAXN + 1];
vector<int> rev[MAXN + 1]; // reverse edges
int xy[MAXN + 5][2];
bool inGraph[MAXN + 5]; // can be reached from any of the west
void dfs1(int x) {
	inGraph[x] = true;
	for (int c : adj[x]) {
		if (!inGraph[c]) {
			dfs1(c);
		}
	}
}

set<pi> east; // sort east coords top to bot
set<pi> west; // sort east coords top to bot
int eID[MAXN + 5];
bool visited[MAXN + 5];
int top[MAXN + 5]; // highest east it can reach, lower ID
int bot[MAXN + 5]; // lowest east it can reach, higher ID
queue<int> Q; // bfs

int main() {
	int A, B;
	cin >> N >> M >> A >> B;
	for (int i = 1; i <= N; i++) {
		cin >> xy[i][0] >> xy[i][1];
	}
	for (int m = 0; m < M; m++) {
		int a, b, k;
		cin >> a >> b >> k;
		adj[a].push_back(b);
        rev[b].push_back(a);
		if (k == 2) {
			adj[b].push_back(a);
			rev[a].push_back(b);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (xy[i][0] == 0) {
			dfs1(i);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (xy[i][0] == A) {
			if (inGraph[i]) east.insert({ -xy[i][1], i });
		}
	}
	int count = 0;
    fill(top, top + MAXN, MAXN + 1);
    fill(bot, bot + MAXN, -MAXN-1);
	for (auto e : east) {
        eID[e.second] = count++;
        top[e.second] = eID[e.second];
        bot[e.second] = eID[e.second];
        Q.push(e.second);
	}
    while (!Q.empty()) {
        int curr = Q.front(); Q.pop();
        for (int c : rev[curr]) {
            if (top[c] <= top[curr] && bot[c] >= bot[curr])continue;
            top[c] = min(top[c], top[curr]);
            bot[c] = max(bot[c], bot[curr]);
            Q.push(c);
        }
    }
    for (int i = 1; i <= N; i++) {
		if (xy[i][0] == 0) {
			if (bot[i] != -MAXN - 1 && top[i] != MAXN + 1) west.insert({ -xy[i][1], bot[i] - top[i] + 1 });
			else west.insert({-xy[i][1], 0});
		}
	}
	for (auto e : west) {
		if(N >= 300000) cout << e.second << endl;
	}
}

• 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