oj.uz

Submission #1110455

# Submission time Handle Problem Language Result Execution time Memory
1110455 2024-11-09T13:45:44 Z vjudge1 Traffic (CEOI11_tra) C++17
0 / 100
 429 ms 58176 KB 
// Problem: C - Traffic
// Contest: Virtual Judge - Training tgasks
// URL: https://vjudge.net/contest/670796#problem/C
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 3e5+1;

int n, m, cx, cy;
array<int, 2> a[N];

vector<int> adj[N], revadj[N];

vector<int> jrkl, hdedh, p_hd, p_jr;
bool is_zero[N];
int rng_l[N], rng_r[N];

bool vis[N];
void dfs(int node) {
	vis[node] = 1;
	for (int ch : adj[node]) {
		if (!vis[ch])
			dfs(ch);
	}
}

void rev_dfs(int node) {
	vis[node] = 1;
	for (int ch : revadj[node]) {
		if (!vis[ch])
			rev_dfs(ch);
	}
} 

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> cx >> cy;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0] >> a[i][1];
		if (a[i][0] == 0)
			jrkl.push_back(i);
		if (a[i][0] == cx)
			hdedh.push_back(i);
	}
	
	sort(jrkl.begin(), jrkl.end(), [](int i, int j) {
		return a[i][1] < a[j][1];
	});
	sort(hdedh.begin(), hdedh.end(), [](int i, int j) {
		return a[i][1] < a[j][1];
	});
	
	for (int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		adj[u].push_back(v);
		revadj[v].push_back(u);
		if (d == 2) {
			adj[v].push_back(u);
			revadj[u].push_back(v);
		}
	}
	
	// remove the zeros from both sides (jrkl and hdedh)
	for (int i : jrkl)
		if (!vis[i])
			dfs(i);
	for (int i : hdedh)
		if (!vis[i])
			is_zero[i] = 1;
	memset(vis, 0, sizeof vis);
	
	for (int i : hdedh)
		if (!vis[i])
			rev_dfs(i);
	for (int i : jrkl)
		if (!vis[i])
			is_zero[i] = 1;
	memset(vis, 0, sizeof vis);
	
	for (int i : jrkl)
		if (!is_zero[i])
			p_jr.push_back(i);
	
	for (int i : hdedh)
		if (!is_zero[i])
			p_hd.push_back(i);
	
	// find rng_r
	int hd_ptr = 0;
	for (int i : p_jr) {
		dfs(i);
		while (hd_ptr+1 < p_hd.size() && vis[p_hd[hd_ptr+1]])
			hd_ptr++;
		rng_r[i] = hd_ptr;
	}
	memset(vis, 0, sizeof vis);
	
	reverse(p_jr.begin(), p_jr.end());
	hd_ptr = p_hd.size()-1;
	for (int i : p_jr) {
		dfs(i);
		while (hd_ptr-1 > 0 && vis[p_hd[hd_ptr-1]])
			hd_ptr--;
		rng_l[i] = hd_ptr;
	}
	
	reverse(jrkl.begin(), jrkl.end());
	for (int i : jrkl) {
		if (is_zero[i]) cout << "0\n";
		else {
			//cerr << rng_l[i] << ' ' << rng_r[i] << '\n';
			cout << rng_r[i] - rng_l[i] + 2 << '\n';	
		}
	}
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   while (hd_ptr+1 < p_hd.size() && vis[p_hd[hd_ptr+1]])
      |          ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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

Subtask #12
0 / 9.0

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