oj.uz

Submission #522135

# Submission time Handle Problem Language Result Execution time Memory
522135 2022-02-03T23:19:47 Z DanerZein Aesthetic (NOI20_aesthetic) C++14
20 / 100
 2000 ms 28828 KB 
#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;
    if(u==a[v]) y=b[v];
    else y=a[v];
    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[v]);
  }
}
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){
	memset(bri,0,sizeof bri);
	for(int i=0;i<path.size();i++){
	  if(path[i].second!=m-1)
	    bri[path[i].second]=1;
	}
        int u=n-1;
	while(u!=0){
	  ll mi=MAX;
	  int id=-1,i2=-1;
	  for(auto &v:G[u]){
	    if(!bri[v]){
	      int y=otro(v,u);
	      if(mi>dis[y]){
		mi=dis[y];
		id=i2=-1;
	      }
	      if(mi==dis[y]){
	        if(v!=m-1) id=y;
		else i2=y;
	      }
	    }
	  }
	  if(id==-1 && i2==-1) break;
	  if(id==-1) u=i2;
	  else
	    u=id;
	}
	res=dis[n-1];
	if(u!=0) res++;
	
      }
      else{
	
      }
    }
    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

Aesthetic.cpp: In function 'std::vector<std::pair<long long int, int> > bfs(int)':
Aesthetic.cpp:47:9: warning: unused variable 'k' [-Wunused-variable]
   47 |     int k=pq.top().first;
      |         ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:107: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]
  107 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~
Aesthetic.cpp:118: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]
  118 |  for(int i=0;i<path.size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 369 ms 836 KB Output is correct
10 Correct 372 ms 756 KB Output is correct
11 Correct 245 ms 748 KB Output is correct
12 Correct 274 ms 752 KB Output is correct
13 Correct 168 ms 720 KB Output is correct
14 Correct 172 ms 716 KB Output is correct
15 Correct 174 ms 716 KB Output is correct
16 Correct 199 ms 716 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 28184 KB Output is correct
2 Correct 508 ms 28280 KB Output is correct
3 Correct 507 ms 28008 KB Output is correct
4 Correct 477 ms 28136 KB Output is correct
5 Correct 538 ms 28040 KB Output is correct
6 Correct 506 ms 28688 KB Output is correct
7 Correct 482 ms 28544 KB Output is correct
8 Correct 523 ms 28828 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 532 ms 28756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 25652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 25652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 369 ms 836 KB Output is correct
10 Correct 372 ms 756 KB Output is correct
11 Correct 245 ms 748 KB Output is correct
12 Correct 274 ms 752 KB Output is correct
13 Correct 168 ms 720 KB Output is correct
14 Correct 172 ms 716 KB Output is correct
15 Correct 174 ms 716 KB Output is correct
16 Correct 199 ms 716 KB Output is correct
17 Correct 480 ms 28184 KB Output is correct
18 Correct 508 ms 28280 KB Output is correct
19 Correct 507 ms 28008 KB Output is correct
20 Correct 477 ms 28136 KB Output is correct
21 Correct 538 ms 28040 KB Output is correct
22 Correct 506 ms 28688 KB Output is correct
23 Correct 482 ms 28544 KB Output is correct
24 Correct 523 ms 28828 KB Output is correct
25 Incorrect 532 ms 28756 KB Output isn't correct
26 Halted 0 ms 0 KB -