Submission #261270

#	Time	Username	Problem	Language	Result	Execution time	Memory
261270		Berted	Aesthetic (NOI20_aesthetic)	C++14	35 / 100	2099 ms	54032 KiB

Aesthetic

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <bitset>
#define ll long long
#define vi vector<int>
#define pii pair<ll, int>
#define fst first
#define snd second
#define pub push_back
#define vpi vector<pii>

using namespace std;

namespace fastIO
{
	char outString[64];
	//inline int getchar_unlocked() {return getchar();}
	//inline void putchar_unlocked(int x) {putchar(x);}
	inline int charInput() {return getchar_unlocked();}
	inline void charOutput(int x) {putchar_unlocked(x);}
	inline bool isNum(int c) {return '0' <= c && c <= '9';}
	inline int intInput()
	{
		int c = 0, ret = 0; bool neg = 0;
		while (!isNum(c)) 
		{
			c = getchar_unlocked();
			if (c == '-') {neg = 1;}
		}
		while (isNum(c)) {ret = ret * 10 + c - '0'; c = getchar_unlocked();}
		return (neg) ? -ret : ret;
	}
	inline void intOutput(ll x)
	{
		int ss = 0;
		while (x) {outString[ss++] = x % 10 + '0'; x /= 10;}
		if (!ss) outString[ss++] = '0';
		for (int i = ss - 1; i >= 0; i--) putchar_unlocked(outString[i]);
	}
	inline void strOutput(string s)
	{
		for (auto &c : s) putchar_unlocked(c);
	}
}

const ll INF = 1e17;

int n, m, pref[300069], cst[300069], idx = 0, vis[300069], low[300069], clr[300069];
vpi adj[300069];
pii edge[300069];
ll dst[2][300069], de[2][300069], lim;
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool ans = 0;

inline void runDijkstra(int s, int id)
{
	for (int i = 0; i < n; i++) dst[id][i] = INF;
	dst[id][s] = 0;
	pq.push({0, s});
	while (pq.size())
	{
		ll d = pq.top().fst; int u = pq.top().snd; pq.pop();
		if (d == dst[id][u])
		{
			for (auto v : adj[u])
			{
				if (dst[id][u] + cst[v.fst] < dst[id][v.snd])
				{
					dst[id][v.snd] = dst[id][u] + cst[v.fst];
					pq.push({dst[id][v.snd], v.snd});
				}
			}
		}
	}
}

void bCheck(int u, int p)
{		
	clr[idx] = u;
	vis[u] = low[u] = idx++;
	for (auto v : adj[u])
	{
		if (v.snd != p && de[0][v.fst] <= lim)
		{
			if (vis[v.snd] == -1)
			{
				bCheck(v.snd, u);
				if (ans) return;
				low[u] = min(low[v.snd], low[u]);
			}
			else low[u] = min(vis[v.snd], low[u]);
			
			if (low[v.snd] > vis[u] && (vis[n - 1] != -1 && low[v.snd] <= vis[n - 1]) && de[1][v.fst] > lim) {ans = 1; return;}
		}
	}
}

int32_t main()
{
	// ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("5-1.in", "r", stdin);
	n = fastIO :: intInput();
	m = fastIO :: intInput();
	for (int i = 0; i < n; i++) vis[i] = -1;
	for (int i = 0; i < m; i++)
	{
		int u, v, w; 
		
		u = fastIO :: intInput();
		v = fastIO :: intInput();
		w = fastIO :: intInput();

		u--; v--;
		adj[u].push_back({i, v});
		adj[v].push_back({i, u});
		cst[i] = pref[i] = w;
		edge[i] = {u, v};
	}
	for (int i = m - 2; i >= 0; i--) {pref[i] = max(pref[i], pref[i + 1]);}
	runDijkstra(0, 0);
	runDijkstra(n - 1, 1);
	for (int i = 0; i < m; i++) 
	{
		de[0][i] = min(dst[0][edge[i].fst] + dst[1][edge[i].snd], dst[1][edge[i].fst] + dst[0][edge[i].snd]) + cst[i];
		de[1][i] = de[0][i] + pref[i + 1];
	}
	int L = 0, R = 1000000000;
	while (L < R)
	{
		int M = L + R >> 1; idx = 0; lim = dst[0][n - 1] + M; ans = 0;
		bCheck(0, -1);
		if (ans) L = M + 1;
		else R = M;
		for (int i = 0; i < idx; i++) {vis[clr[i]] = -1;}
	}
	fastIO :: intOutput(L + dst[0][n - 1]);
	fastIO :: charOutput('\n');
	return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int32_t main()':
Aesthetic.cpp:132:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1; idx = 0; lim = dst[0][n - 1] + M; ans = 0;
           ~~^~~

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