oj.uz

Submission #682121

# Submission time Handle Problem Language Result Execution time Memory
682121 2023-01-15T20:48:37 Z as111 Traffic (CEOI11_tra) C++14
0 / 100
 1192 ms 44644 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 16724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 16764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 17676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 19504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 21948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 23608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 27156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 549 ms 33032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1192 ms 44644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 27152 KB Output isn't correct
2 Halted 0 ms 0 KB -