Submission #546496

#TimeUsernameProblemLanguageResultExecution timeMemory
546496stefantagaBitaro’s Party (JOI18_bitaro)C++14
0 / 100
2068 ms7472 KiB
#include <bits/stdc++.h> using namespace std; vector <int> v[100005],inv[100005]; int n,m,q,i,fr[100005],val[100005],distfin[100005],teste; pair <int,int > dist[100005][305]; int mar[100005]; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n>>m>>teste; for (i=1;i<=m;i++) { int x,y; cin>>x>>y; if (x>y) { swap(x,y); } inv[y].push_back(x); } int bucket = sqrt(n); for (i=1;i<=n;i++) { int numar=0; pair <int,int> acum[305]; for (int j=0;j<inv[i].size();j++) { int nod = inv[i][j]; for (int k=1;k<=mar[i];k++) { fr[dist[i][k].first]=0; } for (int k=1;k<=mar[nod];k++) { fr[dist[nod][k].first]=0; } int st = 0 ,dr=0; while (numar<bucket&&st<=mar[i]&&dr<=mar[nod]) { if (fr[dist[i][st].first]==1) { st++; continue; } if (fr[dist[nod][dr].first]==1) { dr++; continue; } pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr]; if (dist[i][st].second>=dist[nod][dr].second+1) { fr[dist[i][st].first]=1; acum[++numar]={dist[i][st].first,dist[i][st].second}; st++; } else { fr[dist[nod][dr].first]=1; acum[++numar]={dist[nod][dr].first,dist[nod][dr].second+1}; dr++; } } while (numar<bucket&&st<=mar[i]) { if (fr[dist[i][st].first]==1) { st++; continue; } acum[++numar]={dist[i][st].first,dist[i][st].second}; st++; } while (numar<bucket&&dr<=mar[nod]) { if (fr[dist[nod][dr].first]==1) { dr++; continue; } acum[++numar]={dist[nod][dr].first,dist[nod][dr].second+1}; dr++; } mar[i]=numar; for (j=1;j<=numar;j++) { dist[i][j]=acum[j]; } } if (mar[i]<bucket) { dist[i][++mar[i]]={i,0}; } } for (i=1;i<=n;i++) { fr[i]=0; } for (;teste--;) { int nod,nr; cin>>nod >> nr; for (i=1;i<=nr;i++) { cin>>val[i]; fr[val[i]]=1; } if (nr>=bucket) { queue <int> q; for (int j=1;j<=n;j++) { distfin[j]=0; } distfin[nod]=1; q.push(nod); while (!q.empty()) { int acum = q.front(); q.pop(); for (int j =0;j<inv[acum].size();j++) { int nod2 = inv[acum][j]; if (distfin[nod2]<distfin[acum]+1) { distfin[nod2]=distfin[acum]+1; q.push(nod2); } } } int solfin = -1; for (int j=1;j<=n;j++) { if (fr[j]==0&&distfin[j]-1>solfin) { solfin=distfin[j]-1; } } cout<<solfin<<'\n'; } else { int solfin=-1; for (int j=1;j<=mar[nod];j++) { int nod2 = dist[nod][j].first; if (fr[nod2]==0) { solfin=max(solfin,dist[nod][j].second); } } cout<<solfin<<'\n'; } for (i=1;i<=nr;i++) { fr[val[i]]=0; } } return 0; }

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j=0;j<inv[i].size();j++)
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:56:32: warning: variable 'stanga' set but not used [-Wunused-but-set-variable]
   56 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                ^~~~~~
bitaro.cpp:56:53: warning: variable 'dreapta' set but not used [-Wunused-but-set-variable]
   56 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                                     ^~~~~~~
bitaro.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (int j =0;j<inv[acum].size();j++)
      |                               ~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...