Submission #1092207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092207		Trisanu_Das	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	1086 ms	59720 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ff first
#define ss second

int n, m;
vector<pair<int, int> > adj[300005];
pair<int, int> edge[300005];
int w[300005], p[300005], fw[300005], bw[300005], in[300005], low[300005];
priority_queue<pair<int, int> ,vector<pair<int, int> >, greater<pair<int, int> > > pq;
bool used[300005], dc[300005];
int T;
vector<int> bridge;
 
 
 
void dfs(int u, int p){
	in[u] = low[u] = T++;
	if (u == n) dc[u] = true;
	for (auto &it : adj[u]){
		if (it.ff == p || !used[it.ss]) continue;
		if (!in[it.ff]){
			dfs(it.ff, u);
			low[u] = min(low[u], low[it.ff]);
			if (dc[it.ff]){
				if (in[it.ff]==low[it.ff]) bridge.push_back(it.ss);
				dc[u] = true;
            }
		} else low[u] = min(low[u], in[it.ff]);
	}
}
 

bool chk(int i){
	if (i < fw[n]) return true;
	for(int x = 0; x < m; x++)
		used[x]=(fw[edge[x].ff] + w[x] + bw[edge[x].ss] <= i || 
				 fw[edge[x].ss] + w[x] + bw[edge[x].ff] <= i);
	T = 1;
	bridge.clear();
	memset(in, 0, sizeof(in));
	memset(dc, false, sizeof(dc));
	dfs(1,-1);
	for (auto &it : bridge)
		if (fw[edge[it].ff] + w[it] + p[it] + bw[edge[it].ss] > i &&
			fw[edge[it].ss] + w[it] + p[it] + bw[edge[it].ff] > i) return true;
	return false;
 
}

 
signed main(){
 	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int x = 0; x < m; x++){
		cin >> edge[x].ff >> edge[x].ss >> w[x];
		adj[edge[x].ff].push_back({edge[x].ss, x});
		adj[edge[x].ss].push_back({edge[x].ff,x});
	}
	for(int x = m - 1; x > -1; x--) p[x] = max(p[x + 1], w[x + 1]);
	memset(fw, 63, sizeof(fw));
	fw[1] = 0;
	pq.push({fw[1], 1});
	while (!pq.empty()){
		int node = pq.top().ss, weight = pq.top().ff;
		pq.pop();
		if (fw[node]!=weight) continue;
		for (auto &it : adj[node]){
			if (fw[it.ff] > weight + w[it.ss]){
				fw[it.ff] = weight + w[it.ss]; 
				if (it.ff != n) pq.push({fw[it.ff], it.ff});
			}
		}
	}
	memset(bw, 63, sizeof(bw));
	bw[n] = 0;
	pq.push({bw[n],n});
	while (!pq.empty()){
		int node = pq.top().ss, weight=pq.top().ff;
		pq.pop();
		if (bw[node] != weight) continue;
		for (auto &it : adj[node]){
			if (bw[it.ff] > weight + w[it.ss]){
				bw[it.ff] = weight + w[it.ss];
				if (it.ff != 1) pq.push({bw[it.ff], it.ff});
			}
		}
	}
	int lo = fw[n] - 1, hi = fw[n] + 1e9 + 10, mid;
	while (hi - lo > 1){
		mid  = (hi + lo) / 2;
		if (chk(mid)) lo = mid;
		else hi = mid;
	}
	cout << hi << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27