Submission #584378

#TimeUsernameProblemLanguageResultExecution timeMemory
584378urd05Wild Boar (JOI18_wild_boar)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; int n,m,t,l; typedef pair<long long,long long> P; vector<P> adj[4001]; int arr[100001]; long long dp[100001]; long long dp0[100001]; int pos[100001]; bool vis[4001]; long long dist[4001]; const long long INF=1e18; long long c[2002]; long long d[2002]; typedef pair<P,int> Pi; typedef pair<P,P> PP; void dijk(int st,int en,int a,int b) { priority_queue<P,vector<P>,greater<P>> pq; pq.push(P(0,st)); for(int i=1;i<=n+1;i++) { vis[i]=false; dist[i]=INF; } dist[st]=0; while (!pq.empty()) { P now=pq.top(); pq.pop(); if (vis[now.second]) { continue; } //printf("..%d\n",now.second); vis[now.second]=true; if (now.second==en) { continue; } for(int i=0;i<adj[now.second].size();i++) { int nt=adj[now.second][i].first; if (now.second==a&&nt==b) { continue; } if (nt==a&&now.second==b) { continue; } if (dist[nt]>dist[now.second]+adj[now.second][i].second) { dist[nt]=dist[now.second]+adj[now.second][i].second; pq.push(P(dist[nt],nt)); //printf("%d %lld %d %lld %lld\n",now.second,dist[nt],nt,dist[now.second],adj[now.second][i].second); } } } } int main(void) { scanf("%d %d %d %d",&n,&m,&t,&l); for(int i=0;i<m;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); adj[u].push_back(P(v,w)); adj[v].push_back(P(u,w)); } for(int i=1;i<=n;i++) { c[i]=INF; for(int j=0;j<adj[i].size();j++) { int nt=adj[i][j].first; dijk(i,nt,i,nt); c[i]=min(c[i],dist[nt]+adj[i][j].second); } } for(int i=1;i<=l;i++) { scanf("%d",&arr[i]); } int p,q; scanf("%d %d",&p,&q); arr[p]=q; dp[1]=0; dp0[1]=0; pos[1]=arr[1]; for(int i=2;i<=l;i++) { int now=arr[i]; if (i!=l&&adj[now].size()==1) { printf("-1"); return 0; } adj[n+1].clear(); for(int i=1;i<=n;i++) { adj[n+1].push_back(P(i,c[i])); for(int j=0;j<adj[i].size();j++) { adj[i][j].second*=2; } } dijk(n+1,now,0,0); for(int i=1;i<=n;i++) { d[i]=dist[i]; for(int j=0;j<adj[i].size();j++) adj[i][j].second/=2; } vector<long long> vec(adj[now].size()); dijk(arr[i-1],arr[i],0,0); for(int j=0;j<adj[now].size();j++) { int nt=adj[now][j].first; vec[j]=dist[nt]+adj[now][j].second+dp0[i-1]; } dijk(arr[i-1],arr[i],pos[i-1],arr[i-1]); for(int j=0;j<adj[now].size();j++) { int nt=adj[now][j].first; if (nt==arr[i-1]&&arr[i]==pos[i-1]) { continue; } vec[j]=min(vec[j],dist[nt]+adj[now][j].second+dp[i-1]); } long long mn=INF; int ind=now; for(int j=0;j<adj[now].size();j++) { int nt=adj[now][j].first; if (vec[j]<mn) { ind=nt; mn=vec[j]; } } long long mn2=INF; for(int j=0;j<adj[now].size();j++) { int nt=adj[now][j].first; if (adj[now][j].first!=ind) { mn2=min(mn2,vec[j]); mn2=min(mn2,mn+d[nt]+adj[now][j].second*2); } } long long co=INF; for(int bit=0;bit<9;bit++) { vector<PP> save; vector<int> target; vector<P> pr=adj[now]; for(int j=0;j<adj[now].size();j++) { if ((j+save.size())&(1<<bit)) { int nt=adj[now][j].first; if (nt==ind) { continue; } adj[now].erase(adj[now].begin()+j); for(int k=0;k<adj[nt].size();k++) { if (adj[nt][k].first==now) { adj[nt].erase(adj[nt].begin()+k); save.push_back(PP(P(now,nt),P(adj[now][j].second,k))); break; } } j--; } } adj[now]=pr; reverse(save.begin(),save.end()); dijk(now,0,now,ind); for(int j=0;j<save.size();j++) { adj[save[j].first.second].insert(adj[save[j].first.second].begin()+save[j].second.second,P(save[j].first.first,save[j].second.first)); co=min(co,dist[save[j].first.second]+save[j].second.first); } } dp[i]=mn; dp0[i]=min(mn2,mn+co); pos[i]=ind; //printf("%lld %lld %d\n",dp[i],dp0[i],ind); } printf("%lld",dp[l]>=INF?-1:dp[l]); }

Compilation message (stderr)

wild_boar.cpp: In function 'void dijk(int, int, int, int)':
wild_boar.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0;i<adj[now.second].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j=0;j<adj[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
wild_boar.cpp:89:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 | for(int j=0;j<adj[i].size();j++) {
      |             ~^~~~~~~~~~~~~~
wild_boar.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 | for(int j=0;j<adj[i].size();j++) adj[i][j].second/=2;
      |             ~^~~~~~~~~~~~~~
wild_boar.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int j=0;j<adj[now].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~
wild_boar.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j=0;j<adj[now].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~
wild_boar.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int j=0;j<adj[now].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~
wild_boar.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int j=0;j<adj[now].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~
wild_boar.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(int j=0;j<adj[now].size();j++) {
      |                         ~^~~~~~~~~~~~~~~~
wild_boar.cpp:141:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |                     for(int k=0;k<adj[nt].size();k++) {
      |                                 ~^~~~~~~~~~~~~~~
wild_boar.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for(int j=0;j<save.size();j++) {
      |                         ~^~~~~~~~~~~~
wild_boar.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d %d %d",&n,&m,&t,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
wild_boar.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d %d",&p,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...