#include <bits/stdc++.h>
using namespace std;
pair <int, int> c [300010];
vector <int> g [300010];
vector <int> ob [300010];
vector <int> g2 [300010];
int comp [300010];
int vis [300010];
pair <int, int> dp [300010]; int vis2 [300010];
int sol [300010];
vector <int> kraj;
vector <int> pref;
int n, m, a, b;
stack <int> s;
vector <pair <int, int> > out;
int ind=1;
void dfs (int x){
vis [x]=1;
for (int i=0; i<g [x].size(); i++){
if (!vis [g[x][i]]) dfs (g [x][i]);
}
s.push (x);
return ;
}
void dfs2 (int x){
comp [x]=ind;
for (int i=0; i<ob [x].size(); i++){
if (!comp [ob[x][i]]) dfs2 (ob [x][i]);
}
return ;
}
void find_components (){
for (int i=0; i<n; i++){
if (!vis [i]){
dfs (i);
}
}
int sz=s.size();
while (sz){
int x=s.top();
if (!comp [x]){
dfs2 (x); ind++;
}
sz--;
s.pop();
}
return ;
}
pair <int, int> rek (int x){
if (vis2 [x]) return dp [x];
vis2 [x]=1;
for (int i=0; i<g2 [x].size(); i++) {
pair <int, int> y=rek (g2 [x][i]);
dp [x].first=min (dp [x].first, y.first);
dp [x].second=max (dp [x].second, y.second);
}
return dp [x];
}
int main(){
cin >> n >> m >> a >> b;
for (int i=0; i<n; i++) cin >> c [i].first >> c [i].second;
for (int i=0; i<m; i++){
int x, y, t; cin >> x >> y >> t; x--; y--;
g [x].push_back (y); ob [y].push_back (x);
if (t==2){
g [y].push_back (x); ob [x].push_back (y);
}
}
find_components ();
for (int i=0; i<n; i++){
for (int j=0; j<g [i].size(); j++){
if (comp [i]!=comp [g [i][j]]){
g2 [comp [i]].push_back (comp [g [i][j]]);
}
}
}
for (int i=0; i<ind; i++){
dp [i].first=1e9; dp [i].second=-1;
}
for (int i=0; i<n; i++){
if (c [i].first==a){
kraj.push_back (c [i].second);
dp [comp [i]].first=min (dp [comp [i]].first, c [i].second);
dp [comp [i]].second=max (dp [comp [i]].second, c [i].second);
}
}
sort (kraj.begin(), kraj.end());
for (int i=1; i<ind; i++){
rek (i);
}
for (int i=1; i<ind; i++){
if (dp [i].second==-1){
sol [i]=0; continue;
}
vector<int>::iterator it=upper_bound (kraj.begin(), kraj.end(), dp [i].second); it--;
vector<int>::iterator it2=lower_bound (kraj.begin(), kraj.end(), dp [i].first); it2--;
int pos1=it-kraj.begin(); int pos2=it2-kraj.begin();
//cout << pos1 << " " << pos2 << " " << dp [i].first << " " << dp [i].second << endl;
sol [i]=pos1-pos2;
}
for (int i=0; i<n; i++){
if (c [i].first==0) out.push_back ({c [i].second, sol [comp [i]]});
}
sort (out.rbegin(), out.rend());
for (int i=0; i<out.size(); i++) cout << out [i].second << endl;
return 0;
}
Compilation message
tra.cpp: In function 'void dfs(int)':
tra.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i=0; i<g [x].size(); i++){
| ~^~~~~~~~~~~~~
tra.cpp: In function 'void dfs2(int)':
tra.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=0; i<ob [x].size(); i++){
| ~^~~~~~~~~~~~~~
tra.cpp: In function 'std::pair<int, int> rek(int)':
tra.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i=0; i<g2 [x].size(); i++) {
| ~^~~~~~~~~~~~~~
tra.cpp: In function 'int main()':
tra.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j=0; j<g [i].size(); j++){
| ~^~~~~~~~~~~~~
tra.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i=0; i<out.size(); i++) cout << out [i].second << endl;
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
21356 KB |
Output is correct |
| 2 |
Correct |
12 ms |
21416 KB |
Output is correct |
| 3 |
Correct |
11 ms |
21460 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
21448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
21448 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
21452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
21716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
23708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
25332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
29692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
279 ms |
30040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
396 ms |
36232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
649 ms |
45868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1276 ms |
51404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
422 ms |
39864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
