Submission #262793

#	Time	Username	Problem	Language	Result	Execution time	Memory
262793		Cantfindme	Aesthetic (NOI20_aesthetic)	C++17	0 / 100	2101 ms	42252 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

const int maxn = 300010;

int n,e;
vector <pi> adjlist[maxn];
int A[maxn], B[maxn], cost[maxn];
int worst[maxn];

int dist[2][maxn]; //node 1 to any node, and node n to any node

void precalc(int start, int type) {
	memset(dist[type],-1,sizeof dist[type]);
	dist[type][start] = 0;
	priority_queue<pi,vector<pi>,greater<pi>> pq;
	pq.push(pi(0,start));
	
	while (!pq.empty()) {
		pi cur = pq.top(); pq.pop();
		int d = cur.f, x = cur.s;
		if (dist[type][x] != d) continue;
		for (auto i: adjlist[x]) {
			if (dist[type][i.f] == -1 or dist[type][i.f] > d + cost[i.s]) {
				dist[type][i.f] = d + cost[i.s];
				pq.push(pi(dist[type][i.f],i.f));
			}
		}
	}
}

int insmallpath[maxn];
int isbridge[maxn],canboost[maxn];
bool vis[maxn];
bool works;

int co;
int timev[maxn], lowv[maxn];
void findbridges(int x, int p) {
	timev[x] = lowv[x] = co++;
	for (auto cure: adjlist[x]) {
		int i = cure.f, index = cure.s;
		
		if (insmallpath[index] == 0) continue;
		if (i == p) continue;
		
		if (timev[i] != -1) {
			lowv[x] = min(lowv[x], lowv[i]);
		} else {
			findbridges(i,x);
			lowv[x] = min(lowv[x], lowv[i]);
			if (lowv[i] >= timev[x]) {
				//cout << "BRIDGE: " << index << " " << A[index] << " " << B[index] << " " << canboost[index] << "\n";
				if (canboost[index]) isbridge[index] = true;
			}
		}
	}
}

void dfs(int x, int p) {
	vis[x] = 1;
	if (x == n) {
		works = false;
		return;
	}
	for (auto i: adjlist[x]) {
		if (i.f == p) continue;
		if (isbridge[i.s] == 1 or insmallpath[i.s] == 0) continue;
		if (vis[i.f]) continue;
		dfs(i.f,x);
	}
}

bool test(int L) { //Returns true if we can make the shortest path more than L.
	for (int i =0;i<e;i++) {
		if (dist[0][A[i]] + cost[i] + dist[1][B[i]] <= L) insmallpath[i] = 1;
		else if (dist[1][A[i]] + cost[i] + dist[0][B[i]] <= L) insmallpath[i] = 1;
		else insmallpath[i] = 0;
	}
	
	//for (int i =0;i<e;i++) {
		//cout << A[i] << " " << B[i] << " " << insmallpath[i] << "\n";
	//}
	
	for (int i =0;i<e;i++) {
		if (dist[0][A[i]] + cost[i] + worst[i] + dist[1][B[i]] > L and dist[1][A[i]] + cost[i] + worst[i] + dist[0][B[i]] > L) canboost[i] = 1;
		else canboost[i] = 0;
	}
	
	co = 0;
	memset(timev,-1,sizeof timev);
	memset(lowv, 0,sizeof lowv);
	memset(isbridge,0,sizeof isbridge);
	findbridges(1,-1);
	
	memset(vis,0,sizeof vis);
	works = true;
	dfs(1,-1);
	if (works) return true;
	else return false;
}

int main() {
	cin >> n >> e;
	for (int i =0;i<e;i++) {
		cin >> A[i] >> B[i] >> cost[i];
		adjlist[A[i]].push_back(pi(B[i],i));
		adjlist[B[i]].push_back(pi(A[i],i));
	}
	
	for (int i =e-1;i>=0;i--) {
		worst[i] = max(worst[i+1], cost[i+1]);
	}
	
	precalc(1,0);
	precalc(n,0);
	
	int high = 1e9;
	int low = dist[0][n];
	
	while (high - low > 1) {
		int mid = (high+low)/2;
		//cout << "NEW: " << mid << " " << low << " " << high << "\n"; 
		if (test(mid)) low = mid;
		else high = mid;
	}
	cout << high;
}

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