oj.uz

Submission #522136

# Submission time Handle Problem Language Result Execution time Memory
522136 2022-02-03T23:24:07 Z DanerZein Aesthetic (NOI20_aesthetic) C++14
20 / 100
 555 ms 31116 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]){
	    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 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 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 2 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 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 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 2 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 357 ms 3100 KB Output is correct
10 Correct 397 ms 3108 KB Output is correct
11 Correct 253 ms 3092 KB Output is correct
12 Correct 290 ms 3104 KB Output is correct
13 Correct 170 ms 3020 KB Output is correct
14 Correct 216 ms 3060 KB Output is correct
15 Correct 193 ms 3060 KB Output is correct
16 Correct 183 ms 3076 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 30484 KB Output is correct
2 Correct 528 ms 30596 KB Output is correct
3 Correct 509 ms 30324 KB Output is correct
4 Correct 506 ms 30280 KB Output is correct
5 Correct 511 ms 30472 KB Output is correct
6 Correct 509 ms 31112 KB Output is correct
7 Correct 493 ms 30880 KB Output is correct
8 Correct 530 ms 31116 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 420 ms 28036 KB Output isn't correct
2 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 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 2 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 2 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 357 ms 3100 KB Output is correct
10 Correct 397 ms 3108 KB Output is correct
11 Correct 253 ms 3092 KB Output is correct
12 Correct 290 ms 3104 KB Output is correct
13 Correct 170 ms 3020 KB Output is correct
14 Correct 216 ms 3060 KB Output is correct
15 Correct 193 ms 3060 KB Output is correct
16 Correct 183 ms 3076 KB Output is correct
17 Correct 540 ms 30484 KB Output is correct
18 Correct 528 ms 30596 KB Output is correct
19 Correct 509 ms 30324 KB Output is correct
20 Correct 506 ms 30280 KB Output is correct
21 Correct 511 ms 30472 KB Output is correct
22 Correct 509 ms 31112 KB Output is correct
23 Correct 493 ms 30880 KB Output is correct
24 Correct 530 ms 31116 KB Output is correct
25 Incorrect 555 ms 31032 KB Output isn't correct
26 Halted 0 ms 0 KB -