// 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 iszero[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])
iszero[i] = 1;
memset(vis, 0, sizeof vis);
for (int i : hdedh)
if (!vis[i])
rev_dfs(i);
for (int i : jrkl)
if (!vis[i])
iszero[i] = 1;
memset(vis, 0, sizeof vis);
for (int i : jrkl)
if (!iszero[i])
p_jr.push_back(i);
for (int i : hdedh)
if (!iszero[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 (iszero[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:25:14: error: 'bool iszero [300001]' redeclared as different kind of entity
25 | bool iszero[N];
| ^
In file included from /usr/include/c++/10/cmath:45,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from tra.cpp:12:
/usr/include/math.h:1048:1: note: previous declaration 'template<class __T> bool iszero(__T)'
1048 | iszero (__T __val)
| ^~~~~~
tra.cpp: In function 'int main()':
tra.cpp:81:10: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
81 | iszero[i] = 1;
| ^
tra.cpp:89:10: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
89 | iszero[i] = 1;
| ^
tra.cpp:93:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
93 | if (!iszero[i])
| ^
tra.cpp:97:14: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
97 | if (!iszero[i])
| ^
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]])
| ~~~~~~~~~^~~~~~~~~~~~~
tra.cpp:121:13: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
121 | if (iszero[i]) cout << "0\n";
| ^
