oj.uz

Submission #522137

# Submission time Handle Problem Language Result Execution time Memory
522137 2022-02-03T23:24:56 Z DanerZein Aesthetic (NOI20_aesthetic) C++14
36 / 100
 1563 ms 1048580 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;
	}
	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{
	
      }
    }
    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 3 ms 2892 KB Output is correct
2 Correct 3 ms 2956 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2892 KB Output is correct
2 Correct 3 ms 2956 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 360 ms 3116 KB Output is correct
10 Correct 364 ms 3104 KB Output is correct
11 Correct 246 ms 3100 KB Output is correct
12 Correct 248 ms 3020 KB Output is correct
13 Correct 166 ms 3020 KB Output is correct
14 Correct 175 ms 3020 KB Output is correct
15 Correct 176 ms 3060 KB Output is correct
16 Correct 183 ms 3072 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 30544 KB Output is correct
2 Correct 477 ms 30640 KB Output is correct
3 Correct 476 ms 30356 KB Output is correct
4 Correct 468 ms 30328 KB Output is correct
5 Correct 511 ms 30436 KB Output is correct
6 Correct 506 ms 31140 KB Output is correct
7 Correct 480 ms 30868 KB Output is correct
8 Correct 531 ms 31136 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 28076 KB Output is correct
2 Correct 283 ms 29304 KB Output is correct
3 Correct 283 ms 21156 KB Output is correct
4 Correct 279 ms 25100 KB Output is correct
5 Correct 295 ms 25232 KB Output is correct
6 Correct 292 ms 25092 KB Output is correct
7 Correct 338 ms 25124 KB Output is correct
8 Correct 292 ms 25124 KB Output is correct
9 Correct 289 ms 25176 KB Output is correct
10 Correct 292 ms 25348 KB Output is correct
11 Correct 291 ms 25440 KB Output is correct
12 Correct 446 ms 32544 KB Output is correct
13 Correct 295 ms 25200 KB Output is correct
14 Correct 246 ms 33088 KB Output is correct
15 Correct 236 ms 33132 KB Output is correct
16 Correct 421 ms 32520 KB Output is correct
17 Correct 431 ms 31524 KB Output is correct
18 Correct 419 ms 32056 KB Output is correct
19 Correct 278 ms 33796 KB Output is correct
20 Correct 285 ms 33824 KB Output is correct
21 Correct 276 ms 33772 KB Output is correct
22 Correct 284 ms 33972 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 28076 KB Output is correct
2 Correct 283 ms 29304 KB Output is correct
3 Correct 283 ms 21156 KB Output is correct
4 Correct 279 ms 25100 KB Output is correct
5 Correct 295 ms 25232 KB Output is correct
6 Correct 292 ms 25092 KB Output is correct
7 Correct 338 ms 25124 KB Output is correct
8 Correct 292 ms 25124 KB Output is correct
9 Correct 289 ms 25176 KB Output is correct
10 Correct 292 ms 25348 KB Output is correct
11 Correct 291 ms 25440 KB Output is correct
12 Correct 446 ms 32544 KB Output is correct
13 Correct 295 ms 25200 KB Output is correct
14 Correct 246 ms 33088 KB Output is correct
15 Correct 236 ms 33132 KB Output is correct
16 Correct 421 ms 32520 KB Output is correct
17 Correct 431 ms 31524 KB Output is correct
18 Correct 419 ms 32056 KB Output is correct
19 Correct 278 ms 33796 KB Output is correct
20 Correct 285 ms 33824 KB Output is correct
21 Correct 276 ms 33772 KB Output is correct
22 Correct 284 ms 33972 KB Output is correct
23 Runtime error 1563 ms 1048580 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2892 KB Output is correct
2 Correct 3 ms 2956 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 360 ms 3116 KB Output is correct
10 Correct 364 ms 3104 KB Output is correct
11 Correct 246 ms 3100 KB Output is correct
12 Correct 248 ms 3020 KB Output is correct
13 Correct 166 ms 3020 KB Output is correct
14 Correct 175 ms 3020 KB Output is correct
15 Correct 176 ms 3060 KB Output is correct
16 Correct 183 ms 3072 KB Output is correct
17 Correct 484 ms 30544 KB Output is correct
18 Correct 477 ms 30640 KB Output is correct
19 Correct 476 ms 30356 KB Output is correct
20 Correct 468 ms 30328 KB Output is correct
21 Correct 511 ms 30436 KB Output is correct
22 Correct 506 ms 31140 KB Output is correct
23 Correct 480 ms 30868 KB Output is correct
24 Correct 531 ms 31136 KB Output is correct
25 Incorrect 481 ms 31108 KB Output isn't correct
26 Halted 0 ms 0 KB -