#include <bits/stdc++.h>
#define DIM 900010
#define DIMBUFF 1000000
#define INF 2000000000
using namespace std;
//FILE *fin = fopen ("date.in","r");
//FILE *fout = fopen ("date.out","w");
FILE *fin = stdin;
FILE *fout = stdout;
vector <int> L[DIM],inv[DIM],est,vest;
vector <pair<int,int> > d;
int f[DIM],viz[DIM],sol[DIM],dr[DIM],st[DIM];
pair <int,int> pct[DIM];
deque <int> c;
int n,m,a,b,x,y,i,j,val,maxi,mini,poz,ok,pos;
char buff[DIMBUFF];
int get_nr(){
while (!(buff[pos] >= '0' && buff[pos] <= '9')){
pos++;
if (pos == DIMBUFF){
fread (buff,1,DIMBUFF,fin);
pos = 0;
}
}
int nr = 0;
while (buff[pos] >= '0' && buff[pos] <= '9'){
nr = nr * 10 + buff[pos] - '0';
pos++;
if (pos == DIMBUFF){
fread (buff,1,DIMBUFF,fin);
pos = 0;
}
}
return nr;
}
void dfs (int nod){
viz[nod] = 1;
if (f[nod] == 2){
if (pct[nod].second > maxi)
maxi = pct[nod].second, poz = nod;
}
for (auto vecin : L[nod]){
if (!viz[vecin])
dfs (vecin);
}
}
void dfs2 (int nod){
viz[nod] = val;
if (f[nod] == 2){
if (pct[nod].second < mini)
mini = pct[nod].second, poz = nod;
}
for (auto vecin : L[nod]){
if (!viz[vecin])
dfs2 (vecin);
}
}
inline int cmp (int a, int b){
return pct[a].second < pct[b].second;
}
int cautare_binara (vector<int> v, int x){
int st = 0, dr = v.size()-1;
while (st <= dr){
int mid = (st+dr)>>1;
if (pct[v[mid]].second == pct[x].second)
return mid;
if (pct[v[mid]].second < pct[x].second)
st = mid+1;
else dr = mid-1;
}
}
int main (){
fread (buff,1,DIMBUFF,fin);
n = get_nr(), m = get_nr(), a = get_nr(), b = get_nr();
//cin>>n>>m>>a>>b;
for (i=1;i<=n;i++){
//cin>>pct[i].first>>pct[i].second;
pct[i].first = get_nr(), pct[i].second = get_nr();
if (pct[i].first == 0)
f[i] = 1; /// vest
if (pct[i].first == a)
f[i] = 2; /// est
}
for (i=1;i<=m;i++){
//cin>>x>>y>>val;
x = get_nr(), y = get_nr(), val = get_nr();
L[x].push_back(y);
inv[y].push_back(x);
if (val == 2){
L[y].push_back(x);
inv[x].push_back(y);
}
}
/// pastrez doar nodurile din dreapta care sunt reachable din stanga
for (i=1;i<=n;i++)
if (f[i] == 1){
c.push_back(i);
viz[i] = 1;
}
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : L[nod]){
if (!viz[vecin]){
viz[vecin] = 1;
c.push_back(vecin);
}}}
for (i=1;i<=n;i++)
if (f[i] == 2 && viz[i])
est.push_back(i);
/// pastrez in stanga doar nodurile care conteaza si din care pot sa ajung in dr
c.clear();
memset (viz,0,sizeof viz);
for (i=1;i<=n;i++)
if (f[i] == 2){
c.push_back(i);
viz[i] = 1;
}
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : inv[nod]){
if (!viz[vecin]){
viz[vecin] = 1;
c.push_back(vecin);
}}}
for (i=1;i<=n;i++)
if (f[i] == 1 && viz[i])
vest.push_back(i);
sort (vest.begin(),vest.end(),cmp);
memset (viz,0,sizeof viz);
for (int i=0;i<vest.size();i++){
maxi = -INF, poz = 0;
dfs (vest[i]);
if (poz)
dr[i] = poz;
else dr[i] = dr[i-1];
}
memset (viz,0,sizeof viz);
for (int i=vest.size()-1;i>=0;i--){
mini = INF, poz = 0;
dfs2 (vest[i]);
if (poz)
st[i] = poz;
else st[i] = st[i+1];
}
sort (est.begin(),est.end(),cmp);
for (i=0;i<vest.size();i++)
sol[vest[i]] = cautare_binara (est,dr[i]) - cautare_binara (est,st[i]) + 1;
for (i=1;i<=n;i++)
if (f[i] == 1)
d.push_back(make_pair(pct[i].second,sol[i]));
sort (d.begin(),d.end());
reverse(d.begin(),d.end());
for (auto it : d)
fprintf(fout,"%d\n",it.second);
//cout<<it.second<<"\n";
return 0;
}
Compilation message
tra.cpp: In function 'int main()':
tra.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i=0;i<vest.size();i++){
| ~^~~~~~~~~~~~
tra.cpp:174:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (i=0;i<vest.size();i++)
| ~^~~~~~~~~~~~
tra.cpp: In function 'int get_nr()':
tra.cpp:23:19: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | fread (buff,1,DIMBUFF,fin);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
tra.cpp:32:19: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | fread (buff,1,DIMBUFF,fin);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
tra.cpp: In function 'int cautare_binara(std::vector<int>, int)':
tra.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
79 | }
| ^
tra.cpp: In function 'int main()':
tra.cpp:83:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | fread (buff,1,DIMBUFF,fin);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
46028 KB |
Output is correct |
2 |
Correct |
28 ms |
46108 KB |
Output is correct |
3 |
Correct |
29 ms |
46052 KB |
Output is correct |
4 |
Correct |
28 ms |
46056 KB |
Output is correct |
5 |
Correct |
27 ms |
46032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
46152 KB |
Output is correct |
2 |
Correct |
27 ms |
46068 KB |
Output is correct |
3 |
Correct |
27 ms |
46060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
46076 KB |
Output is correct |
2 |
Correct |
27 ms |
46084 KB |
Output is correct |
3 |
Correct |
27 ms |
46156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
46316 KB |
Output is correct |
2 |
Correct |
31 ms |
46628 KB |
Output is correct |
3 |
Correct |
29 ms |
46556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
47636 KB |
Output is correct |
2 |
Correct |
169 ms |
51312 KB |
Output is correct |
3 |
Correct |
48 ms |
48808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
49976 KB |
Output is correct |
2 |
Correct |
200 ms |
52588 KB |
Output is correct |
3 |
Correct |
58 ms |
50816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
52436 KB |
Output is correct |
2 |
Correct |
440 ms |
56204 KB |
Output is correct |
3 |
Correct |
193 ms |
54960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
54248 KB |
Output is correct |
2 |
Correct |
350 ms |
55972 KB |
Output is correct |
3 |
Correct |
202 ms |
55616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
57924 KB |
Output is correct |
2 |
Correct |
3427 ms |
61828 KB |
Output is correct |
3 |
Correct |
407 ms |
62020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
322 ms |
64068 KB |
Output is correct |
2 |
Execution timed out |
5064 ms |
70472 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
780 ms |
75616 KB |
Output is correct |
2 |
Execution timed out |
5076 ms |
73192 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
58016 KB |
Output is correct |
2 |
Correct |
4402 ms |
74820 KB |
Output is correct |
3 |
Correct |
609 ms |
69556 KB |
Output is correct |
4 |
Correct |
817 ms |
79532 KB |
Output is correct |