oj.uz

Submission #1110456

# Submission time Handle Problem Language Result Execution time Memory
1110456 2024-11-09T13:47:19 Z vjudge1 Traffic (CEOI11_tra) C++17
100 / 100
 664 ms 62956 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] + 1 << '\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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 4 ms 18932 KB Output is correct
3 Correct 3 ms 19192 KB Output is correct
4 Correct 4 ms 19024 KB Output is correct
5 Correct 5 ms 19024 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19024 KB Output is correct
2 Correct 4 ms 19024 KB Output is correct
3 Correct 4 ms 19024 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19192 KB Output is correct
2 Correct 4 ms 19024 KB Output is correct
3 Correct 4 ms 19024 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19192 KB Output is correct
2 Correct 6 ms 19504 KB Output is correct
3 Correct 6 ms 19280 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19536 KB Output is correct
2 Correct 47 ms 23744 KB Output is correct
3 Correct 21 ms 21328 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21064 KB Output is correct
2 Correct 52 ms 24904 KB Output is correct
3 Correct 30 ms 23548 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22712 KB Output is correct
2 Correct 68 ms 28800 KB Output is correct
3 Correct 133 ms 30056 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 24664 KB Output is correct
2 Correct 87 ms 28596 KB Output is correct
3 Correct 129 ms 30540 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 26440 KB Output is correct
2 Correct 149 ms 34996 KB Output is correct
3 Correct 232 ms 39752 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 32080 KB Output is correct
2 Correct 294 ms 46968 KB Output is correct
3 Correct 286 ms 41332 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 43336 KB Output is correct
2 Correct 276 ms 48564 KB Output is correct
3 Correct 553 ms 56528 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 25928 KB Output is correct
2 Correct 355 ms 51548 KB Output is correct
3 Correct 443 ms 51168 KB Output is correct
4 Correct 664 ms 62956 KB Output is correct