Submission #1110456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110456		vjudge1	Traffic (CEOI11_tra)	C++17	100 / 100	664 ms	62956 KiB

tra

// 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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9