Submission #302377

#	Time	Username	Problem	Language	Result	Execution time	Memory
302377		errorgorn	Aesthetic (NOI20_aesthetic)	C++14	51 / 100	2031 ms	52852 KiB

Aesthetic

//雪花飄飄北風嘯嘯

//天地一片蒼茫



#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

#include <ext/rope>

using namespace std;

using namespace __gnu_pbds;

using namespace __gnu_cxx;

#define ll long long

#define ii pair<ll,ll>

#define iii pair<ii,ll>

#define fi first

#define se second

#define endl '\n'

#define debug(x) cout << #x << " is " << x << endl;



#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

#define all(x) (x).begin(),(x).end()

#define sz(x) (int)(x).size()



ll MAX(ll a){return a;}

ll MIN(ll a){return a;}

template<typename... Args>

ll MAX(ll a,Args... args){return max(a,MAX(args...));}

template<typename... Args>

ll MIN(ll a,Args... args){return min(a,MIN(args...));}



#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>



mt19937 rng(chrono::system_clock::now().time_since_epoch().count());



int n,m;

vector<ii> al[300005];

ii edge[300005];

ll w[300005];

ll p[300005];



ll fw[300005]; //dist 1->i

ll bw[300005]; //dist N->i



priority_queue<ii,vector<ii>,greater<ii> > pq;



bool used[300005];



int TIME;

int in[300005];

int low[300005];

bool dc[300005]; //whether will disconnect vertice 1 and N



vector<int> bridge;



void dfs(int i,int p){

	in[i]=low[i]=TIME++;

	if (i==n) dc[i]=true;

	

	for (auto &it:al[i]){

		if (it.fi==p || !used[it.se]) continue;

		

		if (!in[it.fi]){

			dfs(it.fi,i);

			low[i]=min(low[i],low[it.fi]);

			if (dc[it.fi]){

				if (in[it.fi]==low[it.fi]) bridge.push_back(it.se);

				dc[i]=true;

			}

		}

		else{

			low[i]=min(low[i],in[it.fi]);

		}

	}

}



bool test(ll i){

	if (i<fw[n]) return true;

	

	rep(x,0,m){

		used[x]=(fw[edge[x].fi]+w[x]+bw[edge[x].se]<=i || 

				 fw[edge[x].se]+w[x]+bw[edge[x].fi]<=i);

	}

	

	TIME=1;

	bridge.clear();

	memset(in,0,sizeof(in));

	memset(dc,false,sizeof(dc));

	dfs(1,-1);

	

	for (auto &it:bridge){

		if (fw[edge[it].fi]+w[it]+p[it]+bw[edge[it].se]>i &&

			fw[edge[it].se]+w[it]+p[it]+bw[edge[it].fi]>i) return true;

	}

	

	return false;

}



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);

	

	cin>>n>>m;

	

	rep(x,0,m){

		cin>>edge[x].fi>>edge[x].se>>w[x];

		

		al[edge[x].fi].push_back(ii(edge[x].se,x));

		al[edge[x].se].push_back(ii(edge[x].fi,x));

	}

	

	rep(x,m,0) p[x]=max(p[x+1],w[x+1]);

	

	memset(fw,63,sizeof(fw));

	fw[1]=0;

	pq.push(ii(fw[1],1));

	while (!pq.empty()){

		ll node=pq.top().se,weight=pq.top().fi;

		pq.pop();

		

		if (fw[node]!=weight) continue;

		for (auto &it:al[node]){

			if (fw[it.fi]>weight+w[it.se]){

				fw[it.fi]=weight+w[it.se];

				if (it.fi!=n) pq.push(ii(fw[it.fi],it.fi));

			}

		}

	}

	

	memset(bw,63,sizeof(bw));

	bw[n]=0;

	pq.push(ii(bw[n],n));

	while (!pq.empty()){

		ll node=pq.top().se,weight=pq.top().fi;

		pq.pop();

		

		if (bw[node]!=weight) continue;

		for (auto &it:al[node]){

			if (bw[it.fi]>weight+w[it.se]){

				bw[it.fi]=weight+w[it.se];

				if (it.fi!=1) pq.push(ii(bw[it.fi],it.fi));

			}

		}

	}

	

	ll lo=fw[n]-1,hi=fw[n]+1e9+10,mi;

	

	while (hi-lo>1){

		mi=hi+lo>>1;

		

		if (test(mi)) lo=mi;

		else hi=mi;

	}

	

	cout<<hi<<endl;

}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:295:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  295 |   mi=hi+lo>>1;
      |      ~~^~~

• 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