Submission #1230035

#TimeUsernameProblemLanguageResultExecution timeMemory
1230035vivkostovWild Boar (JOI18_wild_boar)C++20
0 / 100
0 ms840 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const long long int inf=1e18; struct cell { long long int from,to,st; bool operator<(const cell&a)const { return st>a.st; } }; struct query { long long int ind,st; }; bool cmp(query a1,query a2) { return a1.st<a2.st; } int n,m,t,k,b[2005]; cell a[2005]; query c[2005]; vector<cell>v[2005]; long long int used1[6005][2005],par1[6005][2005],used2[6005][2005],par2[6005][2005],ind[2005][2005],lamp[2005]; void dijkstra(int beg,int from,int ind) { cell w,nb; w.from=from; w.to=beg; w.st=0; priority_queue<cell>q; q.push(w); memset(lamp,0,sizeof(lamp)); long long int st; while(q.size()) { w=q.top(); q.pop(); //cout<<w.from<<" "<<w.to<<" "<<used1[ind][w.to]<<" "<<used2[ind][w.to]<<endl; if(lamp[w.to]==2)continue; lamp[w.to]++; for(int i=0;i<v[w.to].size();i++) { nb=v[w.to][i]; if(lamp[w.to]==1) { st=used1[ind][w.to]+v[w.to][i].st; if(nb.to==w.from)continue; } else { st=used2[ind][w.to]+v[w.to][i].st; if(nb.to==w.from)continue; } //cout<<st<<" "<<nb.to<<endl; nb.st=st; if(used1[ind][nb.to]>st||!used1[ind][nb.to]) { //cout<<nb.to<<" !1"<<endl; q.push(nb); used2[ind][nb.to]=used1[ind][nb.to]; par2[ind][nb.to]=par1[ind][nb.to]; used1[ind][nb.to]=st; par1[ind][nb.to]=w.to; } else if(used2[ind][nb.to]>st||!used2[ind][nb.to]) { //cout<<nb.to<<" !2"<<endl; q.push(nb); used2[ind][nb.to]=st; par2[ind][nb.to]=w.to; } } } } void prec() { int br=0; for(int i=1;i<=n;i++) { br++; ind[i][0]=br; dijkstra(i,0,br); } for(int i=1;i<=m;i++) { br++; ind[a[i].to][a[i].from]=br; dijkstra(a[i].to,a[i].from,br); br++; ind[a[i].from][a[i].to]=br; dijkstra(a[i].from,a[i].to,br); } /* for(int i=1;i<=n;i++) { for(int j=0;j<=n;j++) { br=ind[i][j]; cout<<i<<" "<<j<<" | "; for(int z=1;z<=n;z++) { cout<<used1[br][z]<<" "; } cout<<endl; } } */ } query mi[10]; void resh() { long long int ot1=0,ot2=0,p1=0,p2=0,in; for(int i=1;i<k;i++) { if(i==1) { in=ind[b[i]][0]; ot1=used1[in][b[i+1]]; ot2=used2[in][b[i+1]]; p1=par1[in][b[i+1]]; p2=par2[in][b[i+1]]; //cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl; continue; } in=ind[b[i]][p1]; if(used1[in][b[i+1]]==0&&(!p2||used1[ind[b[i]][p2]][b[i+1]]==0)) { cout<<-1<<endl; return; } mi[1].st=ot1+used1[in][b[i+1]]; mi[1].ind=par1[in][b[i+1]]; mi[2].st=ot1+used2[in][b[i+1]]; mi[2].ind=par2[in][b[i+1]]; in=ind[b[i]][p2]; if(!p2)in=ind[n+1][0]; mi[3].st=ot2+used1[in][b[i+1]]; mi[3].ind=par1[in][b[i+1]]; mi[4].st=ot2+used2[in][b[i+1]]; mi[4].ind=par2[in][b[i+1]]; if(mi[1].st==ot1)mi[1].st=inf; if(mi[2].st==ot1)mi[2].st=inf; if(mi[3].st==ot2||!ot2)mi[3].st=inf; if(mi[4].st==ot2||!ot2)mi[4].st=inf; sort(mi+1,mi+5,cmp); ot1=mi[1].st; p1=mi[1].ind; if(mi[2].st!=inf&&mi[2].ind!=p1) { ot2=mi[2].st; p2=mi[2].ind; } else if(mi[3].st!=inf) { ot2=mi[3].st; p2=mi[3].ind; } //cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl; } cout<<ot1<<endl; } void read() { cin>>n>>m>>t>>k; for(int i=1;i<=m;i++) { cin>>a[i].from>>a[i].to>>a[i].st; v[a[i].from].push_back(a[i]); swap(a[i].from,a[i].to); v[a[i].from].push_back(a[i]); } prec(); for(int i=1;i<=k;i++) { cin>>b[i]; } for(int i=1;i<=t;i++) { cin>>c[i].ind>>c[i].st; b[c[i].ind]=c[i].st; resh(); } } int main() { speed(); read(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...