Submission #522138

#	Time	Username	Problem	Language	Result	Execution time	Memory
522138		DanerZein	Aesthetic (NOI20_aesthetic)	C++14	51 / 100	1321 ms	1048584 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];
bool bri[MAX_N],vis[MAX_N];
int num[MAX_N],low[MAX_N];
int it=0;
int otro(int id,int x){
  if(a[id]==x) return b[id];
  else return a[id];
}
void bridge(int u,int p){
  num[u]=low[u]=it++;
  vis[u]=1;
  for(auto &v:G[u]){
    int y=otro(v,u);
    if(!vis[y]){
      bridge(y,u);
      if(low[y]>num[u]){
	bri[v]=1;
      }
      low[u]=min(low[u],low[y]);
    }
    else
      if(y!=p)
	low[u]=min(low[u],num[y]);
  }
}
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);
  bool sw=0;
  for(int i=0;i<m;i++){
    int x,y,z; cin>>x>>y>>z;
    x--; y--;
    if(z!=1) sw=1;
    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;
  vector<ii> path=bfs(0);
  if(m==n-1){
    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{
    if(m==n || !sw){
      if(!sw){
	for(int i=0;i<path.size();i++){
	  if(path[i].second!=m-1)
	    bri[path[i].second]=1;
	}
	ll d[MAX_N];
	for(int i=0;i<n;i++) d[i]=MAX;
	d[0]=0;
	queue<int> q;
	q.push(0);
	while(!q.empty()){
	  int x=q.front();
	  q.pop();
	  for(auto &v:G[x]){
	    if(bri[v]) continue;
	    int y=otro(v,x);
	    if(d[y]>d[x]+1){
	      d[y]=d[x]+1;
	      q.push(y);
	    }
	  }
	}
	res=dis[n-1];
	if(dis[n-1]!=d[n-1]) res++;
      }
      else{
	bridge(0,0);
	bool us[MAX_N];
        for(int i=0;i<path.size();i++){
	  int id=path[i].second;
	  us[id]=1;
	}
	ll s1,s0;
	s1=s0=0;
	for(int i=0;i<m;i++){
	  if(!bri[i]){
	    if(us[i]) s1+=w[i];
	    else s0+=w[i];
	  }
	}
	res=dis[n-1];
	for(int i=0;i<m-1;i++){
	  if(us[i]){
	    if(bri[i]){
	      res=max(res,dis[n-1]+ma[i]);
	    }
	    else{
	      ll rp=min(dis[n-1]-s1+s0,dis[n-1]+ma[i]);
	      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:45:9: warning: unused variable 'k' [-Wunused-variable]
   45 |     int k=pq.top().first;
      |         ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:105: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]
  105 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~
Aesthetic.cpp:115:15: 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]
  115 |  for(int i=0;i<path.size();i++){
      |              ~^~~~~~~~~~~~
Aesthetic.cpp:142:22: 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]
  142 |         for(int i=0;i<path.size();i++){
      |                     ~^~~~~~~~~~~~

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