# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1110454 | vjudge1 | Traffic (CEOI11_tra) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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';
}
}
}