Submission #262830

#	Time	Username	Problem	Language	Result	Execution time	Memory
262830		Cantfindme	Aesthetic (NOI20_aesthetic)	C++17	0 / 100	2083 ms	40388 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 canboost[maxn];
bool works;
 
int co;
int timev[maxn], lowv[maxn];
void dfs(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) {
			dfs(i,x);
			if (lowv[i] > timev[x]) {
				//cout << "BRIDGE: " << index << " " << A[index] << " " << B[index] << " " << canboost[index] << "\n";
				if (timev[n] >= timev[i] and canboost[index]) works = true;
			}
			lowv[x] = min(lowv[x], lowv[i]);
		} else if (i != p) {
			lowv[x] = min(lowv[x], timev[i]);
		}
		
	}
}
 
bool test(int L) { //Returns true if we can make the shortest path more than L.
	works = false;
	
	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);
	dfs(1,-1);
	
	if (works or timev[n] == -1) 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,1);
	
	int high = 1e9;
	int low = dist[0][n]-1;
	
	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