oj.uz

Submission #682120

# Submission time Handle Problem Language Result Execution time Memory
682120 2023-01-15T20:47:27 Z as111 Traffic (CEOI11_tra) C++14
0 / 100
 1192 ms 44736 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) {
		//cout << e.second << endl;
	}
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:84:12: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   84 |  for (auto e : west) {
      |            ^

Subtask #1
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 #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 16648 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 12 ms 16800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 550 ms 33020 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 44736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

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