Submission #468768

#TimeUsernameProblemLanguageResultExecution timeMemory
468768nicolaalexandraTraffic (CEOI11_tra)C++14
16 / 100
1575 ms44104 KiB
#include <bits/stdc++.h> #define DIM 300010 #define INF 2000000000 using namespace std; 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; 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); else ok = 1; } } void dfs2 (int nod, int val){ 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,val); else { if (viz[vecin] < val) ok = 1; } } } 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 (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>m>>a>>b; for (i=1;i<=n;i++){ cin>>pct[i].first>>pct[i].second; 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; 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=0;i<vest.size();i++){ mini = INF, poz = 0, ok = 0; dfs2 (vest[i],i+1); if (ok && i) st[i] = st[i-1]; else st[i] = poz; } 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) cout<<it.second<<"\n"; return 0; }

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i=0;i<vest.size();i++){
      |                  ~^~~~~~~~~~~~
tra.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i=0;i<vest.size();i++){
      |                  ~^~~~~~~~~~~~
tra.cpp:151:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (i=0;i<vest.size();i++)
      |              ~^~~~~~~~~~~~
tra.cpp: In function 'int cautare_binara(std::vector<int>, int)':
tra.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...