Submission #522034

#	Time	Username	Problem	Language	Result	Execution time	Memory
522034		DanerZein	Aesthetic (NOI20_aesthetic)	C++14	20 / 100	2083 ms	35496 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> ii;
typedef vector<int> vi;
const int MAX_N=3e5+10;
const ll MAX=1e15;
ll ma[MAX_N];
ll dis[MAX_N];
vector<vi> G;
vector<ll> a,b,w;
int n,m;
bool pri[MAX_N];
vector<ii> bfs(int u){
  for(int i=0;i<n;i++) dis[i]=MAX;
  dis[u]=0;
  priority_queue<ii, vector<ii>, greater<ii> > pq;
  pq.push(ii(0,u));
  while(!pq.empty()){
    int x=pq.top().second;
    int k=pq.top().first;
    pq.pop();
    for(auto &v:G[x]){
      int y;
      if(x==a[v]) y=b[v];
      else y=a[v];
      if(dis[y]>dis[x]+w[v]){
	dis[y]=dis[x]+w[v];
	pq.push(ii(dis[y],y));
      }
    }
  }
  memset(pri,0,sizeof pri);
  vector<ii> path;
  int st,en;;
  if(u==0) {
    en=0;
    st=n-1;
  }
  else{
    st=0;
    en=n-1;
  }
  u=st;
  while(u!=en){
    int id=-1;
    ll mi=MAX;
    for(auto &v:G[u]){
      int y;
      if(u==a[v]) y=b[v];
      else y=a[v];
      if(mi>dis[y]){
	id=v; mi=dis[y];
      }
    }
    if(u==a[id]) u=b[id];
    else u=a[id];
    
    path.push_back(ii(u,id));
  }
  reverse(path.begin(),path.end());
  return path;
}
int main(){
  cin>>n>>m;
  G.resize(n+1);
  for(int i=0;i<m;i++){
    int x,y,z; cin>>x>>y>>z;
    x--; y--;
    a.push_back(x);
    b.push_back(y);
    w.push_back(z);
    G[x].push_back(i);
    G[y].push_back(i);
  }
  ma[m]=0;
  for(int i=m-1;i>=0;i--){
    ma[i]=max(ma[i+1],w[i+1]);
  }
  ll res=0;
  if(m==n-1){
    vector<ii> path=bfs(0);
    for(int i=0;i<path.size();i++){
      int id=path[i].second;
      if(id==m-1) continue;
      ll rp=dis[n-1]+ma[id];
      res=max(res,rp);
    }
  }
  else{
    for(int i=0;i<m-1;i++){
      w[i]+=ma[i];
      bfs(0);
      res=max(res,dis[n-1]);
      w[i]-=ma[i];
    }
  }
  cout<<res<<endl;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'std::vector<std::pair<long long int, int> > bfs(int)':
Aesthetic.cpp:21:9: warning: unused variable 'k' [-Wunused-variable]
   21 |     int k=pq.top().first;
      |         ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27