oj.uz

Submission #261270

# Submission time Handle Problem Language Result Execution time Memory
261270 2020-08-11T15:40:32 Z Berted Aesthetic (NOI20_aesthetic) C++14
35 / 100
 2000 ms 54032 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 18 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 18 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 7 ms 7680 KB Output is correct
10 Correct 7 ms 7680 KB Output is correct
11 Correct 8 ms 7680 KB Output is correct
12 Correct 8 ms 7704 KB Output is correct
13 Correct 7 ms 7680 KB Output is correct
14 Correct 7 ms 7680 KB Output is correct
15 Correct 6 ms 7680 KB Output is correct
16 Correct 7 ms 7680 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 48668 KB Output is correct
2 Correct 570 ms 48760 KB Output is correct
3 Correct 423 ms 48336 KB Output is correct
4 Correct 550 ms 48376 KB Output is correct
5 Correct 586 ms 48632 KB Output is correct
6 Correct 445 ms 49400 KB Output is correct
7 Correct 598 ms 49100 KB Output is correct
8 Correct 630 ms 49624 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 49528 KB Output is correct
2 Correct 553 ms 48872 KB Output is correct
3 Correct 567 ms 48504 KB Output is correct
4 Correct 590 ms 48760 KB Output is correct
5 Correct 542 ms 48760 KB Output is correct
6 Correct 542 ms 48760 KB Output is correct
7 Correct 574 ms 48760 KB Output is correct
8 Correct 539 ms 49272 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 54032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 54032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 18 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 7 ms 7680 KB Output is correct
10 Correct 7 ms 7680 KB Output is correct
11 Correct 8 ms 7680 KB Output is correct
12 Correct 8 ms 7704 KB Output is correct
13 Correct 7 ms 7680 KB Output is correct
14 Correct 7 ms 7680 KB Output is correct
15 Correct 6 ms 7680 KB Output is correct
16 Correct 7 ms 7680 KB Output is correct
17 Correct 594 ms 48668 KB Output is correct
18 Correct 570 ms 48760 KB Output is correct
19 Correct 423 ms 48336 KB Output is correct
20 Correct 550 ms 48376 KB Output is correct
21 Correct 586 ms 48632 KB Output is correct
22 Correct 445 ms 49400 KB Output is correct
23 Correct 598 ms 49100 KB Output is correct
24 Correct 630 ms 49624 KB Output is correct
25 Correct 560 ms 49528 KB Output is correct
26 Correct 553 ms 48872 KB Output is correct
27 Correct 567 ms 48504 KB Output is correct
28 Correct 590 ms 48760 KB Output is correct
29 Correct 542 ms 48760 KB Output is correct
30 Correct 542 ms 48760 KB Output is correct
31 Correct 574 ms 48760 KB Output is correct
32 Correct 539 ms 49272 KB Output is correct
33 Execution timed out 2099 ms 54032 KB Time limit exceeded
34 Halted 0 ms 0 KB -