oj.uz

Submission #682124

# Submission time Handle Problem Language Result Execution time Memory
682124 2023-01-15T20:53:34 Z as111 Traffic (CEOI11_tra) C++14
8 / 100
 1150 ms 45032 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
void dfs2(int x) {
	visited[x] = true;
	for (int c : adj[x]) {
		if (!visited[c]) dfs2(c);
		top[x] = min(top[x], top[c]);
        bot[x] = max(bot[x], bot[c]);
	}
}
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);
		//visited[e.second] = true;
	}
	/*
    while (!Q.empty()) {
        int curr = Q.front(); Q.pop();
        for (int c : rev[curr]) {
            //if (top[c] <= top[curr] && bot[c] >= bot[curr])continue;
			if (visited[c]) continue;
			visited[c] = true;
            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) {
			dfs2(i);
			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) {
		cout << e.second << endl;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 8 ms 16736 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct

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 Correct 9 ms 16748 KB Output is correct
2 Incorrect 10 ms 16724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16856 KB Output is correct
2 Incorrect 18 ms 17360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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

Subtask #12
0 / 9.0

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