제출 #46948

#제출 시각아이디문제언어결과실행 시간메모리
46948zscoderWild Boar (JOI18_wild_boar)C++17
62 / 100
18057 ms741424 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; vector<pair<int,int> > edges; ll dist[4111][4111]; int n,m,q,L; vector<pair<ii,int> > adj[2111]; vi in[2111]; vi out[2111]; ll orid[2001][2001]; int getid(int a, int b) { return (a*2+b); } const ll INF=ll(1e18); int a[211111]; ll dp[2][5]; ll D[2111][2111][5]; vector<pair<int,int> > paths[2111][2111]; vector<ll> W; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>q>>L; for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; u--; v--; edges.pb({u,v}); W.pb(w); edges.pb({v,u}); W.pb(w); orid[u][v]=orid[v][u]=w; adj[u].pb(mp(mp(v,w),i*2)); adj[v].pb(mp(mp(u,w),i*2+1)); out[u].pb(i*2); out[v].pb(i*2+1); in[u].pb(i*2+1); in[v].pb(i*2); } /* int orim = m; for(int i=0;i<n;i++) { adj[n].pb(mp(mp(i,0),m++)); edges.pb({n,i}); W.pb(0); } */ int orim = m; m*=2; for(int i=0;i<m;i++) { priority_queue<ii,vector<ii>,greater<ii> > pq; int s = i; pq.push(mp(0,s)); for(int k=0;k<m;k++) dist[s][k] = INF; dist[s][s] = 0; while(!pq.empty()) { ll d=pq.top().fi; int u = pq.top().se; pq.pop(); //cerr<<"DIST : "<<s<<' '<<u<<' '<<d<<'\n'; int vertex = edges[u].se; int edgeno = u; for(auto k:adj[vertex]) { int v = k.fi.fi; ll w = k.fi.se; int id = k.se; if(id/2==edgeno/2) continue; int u1 = edges[id].fi; int v1 = edges[id].se; assert(u1==vertex); //if(edges[id][0]!=v) vid++; if(dist[s][id]>d) { dist[s][id] = d; pq.push(mp(d+w, id)); } } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==j) continue; ll mn=INF; ii cur=mp(-1,-1); for(int k:out[i]) { for(int l:in[j]) { if(dist[k][l]+W[k]+W[l]<mn) { mn=dist[k][l]+W[k]+W[l]; cur=mp(edges[k].se, edges[l].fi); } } } if(orid[i][j]>0) { if(orid[i][j]<mn) { mn=orid[i][j]; cur=mp(j,i); } } D[i][j][0] = mn; //D[j][i][0] = mn; paths[i][j].pb(cur); //paths[j][i].pb(cur); mn = INF; cur = mp(-1,-1); for(int k:out[i]) { for(int l:in[j]) { //cerr<<"OUT "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n'; if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn) { //cerr<<"OUT 2 : "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n'; mn=dist[k][l]+W[k]+W[l]; cur=mp(edges[k].se, edges[l].fi); } } } if(orid[i][j]>0) { if(orid[i][j]<mn&&j!=paths[i][j][0].fi) { mn=orid[i][j]; cur=mp(j,i); } } D[i][j][1] = mn; //= D[j][i][1] = mn; paths[i][j].pb(cur); //paths[j][i].pb(cur); mn = INF; cur = mp(-1,-1); for(int k:out[i]) { for(int l:in[j]) { if(edges[k].se!=paths[i][j][0].fi&&edges[l].fi!=paths[i][j][1].se&&dist[k][l]+W[k]+W[l]<mn) { mn=dist[k][l]+W[k]+W[l]; cur=mp(edges[k].se, edges[l].fi); } } } if(orid[i][j]>0) { if(orid[i][j]<mn&&j!=paths[i][j][0].fi&&i!=paths[i][j][1].se) { mn=orid[i][j]; cur=mp(j,i); } } D[i][j][2] = mn; //D[j][i][2] = mn; paths[i][j].pb(cur); //paths[j][i].pb(cur); mn = INF; cur = mp(-1,-1); for(int k:out[i]) { for(int l:in[j]) { if(edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn) { mn=dist[k][l]+W[k]+W[l]; cur=mp(edges[k].se, edges[l].fi); } } } if(orid[i][j]>0) { if(orid[i][j]<mn&&i!=paths[i][j][0].se) { mn=orid[i][j]; cur=mp(j,i); } } D[i][j][3] = mn; // D[j][i][3] = mn; paths[i][j].pb(cur); //paths[j][i].pb(cur); mn = INF; cur = mp(-1,-1); for(int k:out[i]) { for(int l:in[j]) { if(edges[k].se!=paths[i][j][3].fi&&edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn) { mn=dist[k][l]+W[k]+W[l]; cur=mp(edges[k].se, edges[l].fi); } } } if(orid[i][j]>0) { if(orid[i][j]<mn&&j!=paths[i][j][3].fi&&i!=paths[i][j][0].se) { mn=orid[i][j]; cur=mp(j,i); } } D[i][j][4] = mn; //D[j][i][2] = mn; paths[i][j].pb(cur); //paths[j][i].pb(cur); } } for(int i=0;i<L;i++) { cin>>a[i]; a[i]--; } for(int zz=0;zz<q;zz++) { int y,z; cin>>y>>z; y--; z--; a[y]=z; /* for(int i=0;i<m*2;i++) { dp[0][i] = INF; } for(int i=0;i<m;i++) { for(int j=0;j<2;j++) { if(edges[i][j]==a[0]) { dp[0][getid(i,j)] = 0; } } } */ /* dp[0][getid(orim + a[0],1)] = 0; for(int i=0;i+1<L;i++) { int pre = i&1; int cur = pre^1; for(int j=0;j<m*2;j++) { dp[cur][j] = INF; } for(int j=0;j<m*2;j++) { if(dp[pre][j]<INF) { ll v=dp[pre][j]; for(int k:belong[a[i+1]]) { if(dist[j][k]<INF) { dp[cur][k] = min(dp[cur][k], v + dist[j][k]); } } } } } ll mn = INF; for(int i=0;i<m*2;i++) { mn = min(mn, dp[(L+1)&1][i]); } cout<<mn<<'\n'; */ for(int i=0;i<5;i++) dp[1][i] = D[a[0]][a[1]][i]; /* for(int j=0;j<5;j++) { cerr<<0<<' '<<j<<' '<<paths[a[0]][a[1]][j].fi<<' '<<paths[a[0]][a[1]][j].se<<' '<<dp[1][j]<<'\n'; } */ for(int i=1;i+1<L;i++) { int pre = i&1; int cur = pre^1; for(int j=0;j<5;j++) { dp[cur][j]=INF; } for(int j=0;j<5;j++) { if(dp[pre][j]<INF) { ll v=dp[pre][j]; for(int k=0;k<5;k++) { //cerr<<i<<' '<<j<<' '<<k<<' '<<paths[a[i-1]][a[i]][j].fi<<' '<<paths[a[i-1]][a[i]][j].se<<' '<<paths[a[i]][a[i+1]][k].fi<<' '<<paths[a[i]][a[i+1]][k].se<<' '<<D[a[i-1]][a[i]][j]<<' '<<D[a[i]][a[i+1]][k]<<'\n'; if(paths[a[i-1]][a[i]][j].se!=-1&&paths[a[i]][a[i+1]][k].fi!=-1&&paths[a[i-1]][a[i]][j].se!=paths[a[i]][a[i+1]][k].fi) { dp[cur][k] = min(dp[cur][k], v + D[a[i]][a[i+1]][k]); } } } } /* for(int j=0;j<5;j++) { cerr<<i<<' '<<j<<' '<<paths[a[i]][a[i+1]][j].fi<<' '<<paths[a[i]][a[i+1]][j].se<<' '<<dp[cur][j]<<'\n'; } */ } ll mn = INF; for(int i=0;i<5;i++) mn=min(mn,dp[(L+1)&1][i]); if(mn>=INF) mn=-1; cout<<mn<<'\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:74:9: warning: unused variable 'v' [-Wunused-variable]
     int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
         ^
wild_boar.cpp:76:32: warning: unused variable 'v1' [-Wunused-variable]
     int u1 = edges[id].fi; int v1 = edges[id].se;
                                ^~
wild_boar.cpp:59:6: warning: unused variable 'orim' [-Wunused-variable]
  int orim = m; m*=2;
      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...