#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300005
#define MAXM 900005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second
ll n, m, c, MAXX, MAXY, p[MAXN], sz[MAXN], en[MAXN], pfx[MAXN];
pair<ll, ll> vp[MAXN], rng[MAXN];
vector<ll> adj[MAXN], radj[MAXN], ts;
bool vis[MAXN], rw[MAXN];
stack<ll> s;
ll find(ll x){
return (p[x] == x) ? x : (p[x] = find(p[x]));
}
void onion(ll a, ll b){
a = find(a), b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
p[a] = p[b] = a;
}
void dfs1(ll v){
if(vis[v]) return;
vis[v] = true;
for(ll v2 : adj[v]) dfs1(v2);
s.push(v);
}
void dfs2(ll v){
if(vis[v]) return;
vis[v] = true;
for(ll v2 : radj[v]) {
v2 = find(v2);
if(!vis[v2]) onion(v, v2);
dfs2(v2);
}
}
void dfs3(ll v){
if(vis[v]) return;
vis[v] = true;
for(ll v2 : adj[v]){
v2 = find(v2);
dfs3(v2);
}
ts.push_back(v);
}
int main(){
cin >> n >> m >> MAXX >> MAXY;
FOR(i, 1, n) cin >> vp[i].f >> vp[i].s;
FOR(i, 1, m) {
ll a, b, ct; cin >> a >> b >> ct;
adj[a].push_back(b), radj[b].push_back(a);
if(ct == 2) adj[b].push_back(a), radj[a].push_back(b);
}
// Kosarju's
FOR(i, 1, n) vis[i] = false;
FOR(i, 1, n) dfs1(i);
FOR(i, 1, n) vis[i] = false, p[i] = i, sz[i] = 1;
while(!s.empty()){
ll si = s.top(); s.pop();
dfs2(si);
}
// Topological sort
FOR(i, 1, n) {
if(find(i) != i){
ll fi = find(i);
for(ll i2 : adj[i]){
adj[fi].push_back(i2);
}
}
}
FOR(i, 1, n) vis[i] = false;
FOR(i, 1, n) dfs3(find(i));
// sort east nodes by top to bottom y values
vector<pair<ll, ll>> ev;
FOR(i, 1, n) {
if(vp[i].f == MAXX){
ev.push_back({vp[i].s, i});
}else{
en[i] = -1;
}
}
sort(begin(ev), end(ev));
// first topological order run
FOR(i, 1, n) rw[i] = false;
FOR(i, 1, n) rw[find(i)] |= (vp[i].f == 0);
for(ll i = ts.size() - 1; i >= 0; i--){
ts[i] = find(ts[i]);
//cout << "WE HAVE ORDER " << ts[i] << " WITH PRE'S ";
for(ll i2 : radj[ts[i]]) {
rw[ts[i]] |= rw[find(i2)];
//cout << " " << find(i2) << "(" << i2 << ")";
}
//cout << endl;
}
/*FOR(i, 1, n){
cout << "REACH WEST FOR " << i << " IS " << rw[i] << endl;
}*/
// final topological order run
pfx[0] = 0;
FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
FOR(i, 1, n) rng[find(i)] = {LONG_LONG_MAX, LONG_LONG_MIN};
FOR(i, 1, n) {
if(vp[i].f == MAXX && rw[find(i)]) {
rng[find(i)].f = min(rng[find(i)].f, en[i]);
rng[find(i)].s = max(rng[find(i)].s, en[i]);
}
vis[i] = false;
}
FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
for(ll i : ts){
i = find(i);
if(!vis[i]){
vis[i] = true;
for(ll i2 : adj[i]) if(find(i2) != i) {
i2 = find(i2);
rng[i].f = min(rng[i].f, rng[i2].f);
rng[i].s = max(rng[i].s, rng[i2].s);
}
}
}
/*FOR(i, 1, n){
cout << "NODE " << i << " HAS RANGE " << rng[i].f << " to " << rng[i].s << endl;
}*/
set<pair<ll, ll>> st;
FOR(i, 1, n){
if(vp[i].f == 0) st.insert({-vp[i].s, find(i)});
}
for(pair<ll, ll> i : st){
if(rng[i.s].f == LONG_LONG_MAX){
cout << 0 << endl;
}else{
cout << (pfx[rng[i.s].s] - pfx[rng[i.s].f - 1]) << endl;
}
}
}
Compilation message
tra.cpp: In function 'int main()':
tra.cpp:6:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
120 | FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
| ~~~~~~~~~~~~~~~~~~~
tra.cpp:120:5: note: in expansion of macro 'FOR'
120 | FOR(i, 0, ev.size() - 1) en[ev[i].s] = i + 1;
| ^~~
tra.cpp:6:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
129 | FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
| ~~~~~~~~~~~~~~~
tra.cpp:129:5: note: in expansion of macro 'FOR'
129 | FOR(i, 1, ev.size()) pfx[i] = pfx[i - 1] + (rng[ev[i - 1].s].f != LONG_LONG_MAX);
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14380 KB |
Output is correct |
| 4 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 5 |
Correct |
9 ms |
14424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
7 ms |
14560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
18308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
71 ms |
21712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
113 ms |
27956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
177 ms |
33736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
320 ms |
42440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
537 ms |
57808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
955 ms |
93636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
286 ms |
49520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
