#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>
#define ff first
#define ss second
#define PB push_back
#define sz(x) int(x.size())
#define rsz resize
#define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation
#define all(x) (x).begin(),(x).end()
#define eps 1e-9
// more abusive notation (use at your own risk):
//#define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
// debugging
void __print(int x) {std::cerr << x;}
void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */
void __print(unsigned x) {std::cerr << x;}
void __print(ull x) {std::cerr << x;}
void __print(float x) {std::cerr << x;}
void __print(double x) {std::cerr << x;}
void __print(ld x) {std::cerr << x;}
void __print(char x) {std::cerr << '\'' << x << '\'';}
void __print(const char *x) {std::cerr << '\"' << x << '\"';}
void __print(const string& x) {std::cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';}
template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";}
void _print() {std::cerr << "]\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);}
void println() {std::cerr << ">--------------------<" << endl;}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */
// const variables
constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7
void setIO(const string& str) {// fast input/output
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (str.empty()) return;
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
struct SCC {
/*
* Author: William Wang
* Date: 4/17/2024
* Source: https://cp-algorithms.com/graph/strongly-connected-components.html
* Status: Tested on USACO Gold Grass Cownoisseur
* */
int N, C;
vc<vi> adj, adj_;
vc<vi> adjc;
vi vst, order, comp, cc;
SCC() {}
SCC(int n, vc<vi> jda) { // jda = O(M) space, passing by value is fine
N = n;
C = 0;
adj = jda;
vst.clear(), order.clear(), comp.clear(), cc.clear();
vst.rsz(N+1, 0), comp.rsz(N+1), cc.rsz(N+1, -1);
adj_.rsz(N+1);
for (int i = 1; i <= N; ++i) { // change index bounds if needed
while (!jda[i].empty()) {
int u = jda[i].back();
adj_[u].PB(i);
jda[i].pop_back();
}
}
}
void dfs1(int v) {
vst[v] = 1;
for (int u : adj[v]) if (!vst[u]) dfs1(u);
order.PB(v);
}
void dfs2(int v) {
vst[v] = 1;
comp.PB(v);
for (int u : adj_[v]) if (!vst[u]) dfs2(u);
}
void condense() {
vst.clear(), vst.rsz(N+1, 0), adjc.clear(), adjc.rsz(N+1);
for (int i = 1; i <= N; ++i) if (!vst[i]) dfs1(i);
vst.clear(), vst.rsz(N+1, 0);
reverse(all(order));
C = 0;
for (int v : order) {
if (!vst[v]) {
dfs2(v);
for (int u : comp) {
cc[u] = C;
}
comp.clear();
C++;
}
}
for (int i = 1; i <= N; ++i) {
for (int u : adj[i]) {
if (cc[u] != cc[i]) adjc[cc[i]].PB(cc[u]); // reminder: contains duplicates
}
}
}
};
int N, M, A, B, C;
vc<pii> west, east;
vi rem, lo, hi, order, visited;
SCC scc;
vc<vi> adj, adj_;
void bfs() {
queue<int> q;
vi vst(N+1, 0);
for (int i = 0; i < sz(west); ++i) {
vst[west[i].ss] = 1;
q.push(west[i].ss);
}
while (!q.empty()) {
int v = q.front();
q.pop();
fch(u, adj[v]) if (!vst[u]) {
vst[u] = 1;
q.push(u);
}
}
for (int i = 0; i < sz(east); ++i) {
rem[i] = !vst[east[i].ss];
}
}
void dfs(int v) {
visited[v] = 1;
fch(u, adj_[v]) if (!visited[u]) {
dfs(u);
}
order.PB(v);
}
signed main() { // TIME YOURSELF !!!
setIO("");
cin >> N >> M >> A >> B;
adj.rsz(N+1);
for (int i = 1; i <= N; ++i) {
int x, y;
cin >> x >> y;
if (x == 0) {
west.PB({y, i});
} else if (x == A) {
east.PB({y, i});
}
}
rem.rsz(sz(east));
for (int i = 0; i < M; ++i) {
int c, d, k;
cin >> c >> d >> k;
adj[c].PB(d);
if (k == 2) {
adj[d].PB(c);
}
}
sort(all(west)), sort(all(east));
bfs();
scc = SCC(N, adj);
scc.condense();
C = scc.C, adj_ = scc.adjc;
lo.rsz(C, INF), hi.rsz(C, -1), visited.rsz(C, 0);
// for (int i = 1; i <= N; ++i) {
// debug(i, scc.cc[i]);
// }
for (int i = 0; i < sz(east); ++i) {
if (rem[i]) continue;
int v = east[i].ss;
ckmin(lo[scc.cc[v]], i);
ckmax(hi[scc.cc[v]], i);
}
for (int i = 0; i < C; ++i) {
if (!visited[i]) {
dfs(i);
}
}
for (int i = 0; i < sz(order); ++i) {
int c = order[i];
fch(u, adj_[c]) {
ckmin(lo[c], lo[u]);
ckmax(hi[c], hi[u]);
}
}
for (int i = 0; i < sz(east); ++i) {
rem[i] = (i > 0 ? rem[i-1] : 0) + rem[i];
}
for (int i = sz(west)-1; i >= 0; --i) {
int v = west[i].ss;
int l = lo[scc.cc[v]], h = hi[scc.cc[v]];
if (l > h) {
cout << "0\n";
continue;
}
cout << h - l + 1 - (rem[h] - (l > 0 ? rem[l - 1] : 0)) << '\n';
}
return 0;
}
// TLE -> TRY NOT USING DEFINE INT LONG LONG
// CE -> CHECK LINE 45
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler
Compilation message
tra.cpp: In function 'void setIO(const string&)':
tra.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen((str + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen((str + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
456 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8464 KB |
Output is correct |
| 2 |
Correct |
46 ms |
15476 KB |
Output is correct |
| 3 |
Correct |
31 ms |
8336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
13052 KB |
Output is correct |
| 2 |
Correct |
50 ms |
19552 KB |
Output is correct |
| 3 |
Correct |
34 ms |
16200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
26276 KB |
Output is correct |
| 2 |
Correct |
85 ms |
33992 KB |
Output is correct |
| 3 |
Correct |
115 ms |
30616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
27932 KB |
Output is correct |
| 2 |
Correct |
87 ms |
31992 KB |
Output is correct |
| 3 |
Correct |
126 ms |
31432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
48380 KB |
Output is correct |
| 2 |
Correct |
203 ms |
60608 KB |
Output is correct |
| 3 |
Correct |
245 ms |
58576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
79408 KB |
Output is correct |
| 2 |
Correct |
275 ms |
93136 KB |
Output is correct |
| 3 |
Correct |
261 ms |
67972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
408 ms |
95228 KB |
Output is correct |
| 2 |
Correct |
303 ms |
95916 KB |
Output is correct |
| 3 |
Correct |
428 ms |
94488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
70332 KB |
Output is correct |
| 2 |
Correct |
324 ms |
101412 KB |
Output is correct |
| 3 |
Correct |
396 ms |
94708 KB |
Output is correct |
| 4 |
Correct |
438 ms |
99784 KB |
Output is correct |
