oj.uz

Submission #682117

# Submission time Handle Problem Language Result Execution time Memory
682117 2023-01-15T20:05:09 Z as111 Traffic (CEOI11_tra) C++14
0 / 100
 247 ms 23532 KB 
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define MAXN 100000
using namespace std;
int N, M;

set<pair<int, int>> west;
set<int> east;
vector<int> adj[MAXN + 1];
vector<int> rev[MAXN + 1];
stack<int> S;
bool visited[MAXN + 1];

int ID[MAXN + 1];
vector<int> components[MAXN];
int numComponents;
int ans[MAXN + 1];

void dfs1(int x) {
	visited[x] = true;
	for (int i = 0; i < adj[x].size(); i++) {
		if (!visited[adj[x][i]]) dfs1(adj[x][i]);
	}
	S.push(x);
}
void dfs2(int x) {
	ID[x] = numComponents;
	components[numComponents].push_back(x);
	visited[x] = true;
	if (east.count(x)) ans[ID[x]]++;
	for (int i = 0; i < rev[x].size(); i++) {
		if (!visited[rev[x][i]]) dfs2(rev[x][i]);
	}
}

int main() {
	int A, B;
	cin >> N >> M >> A >> B;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		if (x == 0) {
			west.insert({ -y,i });//dec y coords
		}
		if (x == A) {
			east.insert(i);
		}
	}
	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 != 1) {
			adj[b].push_back(a);
			rev[a].push_back(b);
		}
	}
	for (int i = 0; i < N; i++) {
		if (!visited[i]) dfs1(i);
	}
	for (int i = 0; i < N; i++) {
		visited[i] = false;
	}
	while (!S.empty()) {
		int v = S.top();
		S.pop();
		if (!visited[v]) {
			dfs2(v);
			numComponents++;
		}
	}
	for (auto e : west) {
		cout << ans[ID[e.second]] << endl;
	}
}

Compilation message

tra.cpp: In function 'void dfs1(int)':
tra.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0; i < adj[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
tra.cpp: In function 'void dfs2(int)':
tra.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < rev[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 135 ms 18328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 20932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 21644 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 23532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -