oj.uz

답안 #522134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522134 2022-02-03T23:16:33 Z DanerZein Aesthetic (NOI20_aesthetic) C++14
20 / 100
 501 ms 52016 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];
	        if(v!=m-1) id=v;
		else i2=v;
	      }
	    }
	  }
	  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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 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 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 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 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 354 ms 764 KB Output is correct
10 Correct 375 ms 756 KB Output is correct
11 Correct 256 ms 716 KB Output is correct
12 Correct 256 ms 756 KB Output is correct
13 Correct 166 ms 716 KB Output is correct
14 Correct 169 ms 716 KB Output is correct
15 Correct 175 ms 716 KB Output is correct
16 Correct 173 ms 720 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 28268 KB Output is correct
2 Correct 492 ms 28320 KB Output is correct
3 Correct 483 ms 27924 KB Output is correct
4 Correct 485 ms 27944 KB Output is correct
5 Correct 479 ms 28200 KB Output is correct
6 Correct 483 ms 28676 KB Output is correct
7 Correct 486 ms 28616 KB Output is correct
8 Correct 501 ms 28796 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 494 ms 28780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 404 ms 52016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 404 ms 52016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 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 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 354 ms 764 KB Output is correct
10 Correct 375 ms 756 KB Output is correct
11 Correct 256 ms 716 KB Output is correct
12 Correct 256 ms 756 KB Output is correct
13 Correct 166 ms 716 KB Output is correct
14 Correct 169 ms 716 KB Output is correct
15 Correct 175 ms 716 KB Output is correct
16 Correct 173 ms 720 KB Output is correct
17 Correct 483 ms 28268 KB Output is correct
18 Correct 492 ms 28320 KB Output is correct
19 Correct 483 ms 27924 KB Output is correct
20 Correct 485 ms 27944 KB Output is correct
21 Correct 479 ms 28200 KB Output is correct
22 Correct 483 ms 28676 KB Output is correct
23 Correct 486 ms 28616 KB Output is correct
24 Correct 501 ms 28796 KB Output is correct
25 Incorrect 494 ms 28780 KB Output isn't correct
26 Halted 0 ms 0 KB -