Submission #291491

#TimeUsernameProblemLanguageResultExecution timeMemory
291491TadijaSebezWild Boar (JOI18_wild_boar)C++11
0 / 100
155 ms264696 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pb push_back #define ll long long const int N=2005; const int M=200050; const int C=4; const ll inf=4e18; struct path{ int u,v;ll cost; path(int a=0,int b=0,ll c=inf):u(a),v(b),cost(c){} }; bool operator < (path a,path b){return a.cost>b.cost;} path dist[N][N][C]; bool push(path tmp[C],path now){ int i,c1=0,c2=0; for(i=0;i<C&&tmp[i].cost<now.cost;i++){ if(tmp[i].u==now.u&&tmp[i].v==now.v)return 0; c1+=tmp[i].u==now.u; c2+=tmp[i].v==now.v; } if(c1>1||c2>1||i==C)return 0; tmp[i]=now; return 1; } vector<pii> E[N]; int ls[M],rs[M],tsz,root; path node[M][C]; void pull(int c){ for(int i=0;i<C;i++)node[c][i]=path(); vector<path> tmp; for(int j=0;j<C;j++) for(int k=0;k<C;k++) if(node[ls[c]][j].v!=node[rs[c]][k].u) tmp.pb(path(node[ls[c]][j].u,node[rs[c]][k].v,node[ls[c]][j].cost+node[rs[c]][k].cost)); sort(tmp.begin(),tmp.end()); while(tmp.size())push(node[c],tmp.back()),tmp.pop_back(); } int x[M]; void Set(int&c,int ss,int se,int qi){ if(!c)c=++tsz; if(ss==se){ for(int i=0;i<C;i++)node[c][i]=dist[x[ss]][x[ss+1]][i]; return; } int mid=ss+se>>1; if(qi<=mid)Set(ls[c],ss,mid,qi); else Set(rs[c],mid+1,se,qi); pull(c); } int main(){ int n,m,t,l; scanf("%i %i %i %i",&n,&m,&t,&l); for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w}); for(int u=1;u<=n;u++){ priority_queue<pair<path,int>> pq; for(auto e:E[u])pq.push({path(e.first,u,e.second),e.first}); while(pq.size()){ pair<path,int> now=pq.top(); pq.pop(); if(!push(dist[u][now.second],now.first))continue; for(auto e:E[now.second])if(e.first!=now.first.v) pq.push({path(now.first.u,now.second,now.first.cost+e.second),e.first}); } } for(int i=1;i<=l;i++)scanf("%i",&x[i]); for(int i=1;i<l;i++)Set(root,1,l-1,i); while(t--){ int i,y; scanf("%i %i",&i,&y); x[i]=y; if(i!=1)Set(root,1,l-1,i-1); if(i!=l)Set(root,1,l-1,i); ll ans=node[root][0].cost; printf("%lld\n",ans<inf?ans:-1); } return 0; }

Compilation message (stderr)

wild_boar.cpp: In function 'void Set(int&, int, int, int)':
wild_boar.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  int mid=ss+se>>1;
      |          ~~^~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%i %i %i %i",&n,&m,&t,&l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:55:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  for(int i=1;i<=l;i++)scanf("%i",&x[i]);
      |                       ~~~~~^~~~~~~~~~~~
wild_boar.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%i %i",&i,&y);
      |   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...