oj.uz

답안 #261303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261303 2020-08-11T15:59:57 Z Berted Aesthetic (NOI20_aesthetic) C++14
0 / 100
 2000 ms 51028 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <bitset>
#define ll long long
#define vi vector<int>
#define pii pair<ll, int>
#define ppi pair<ll, pii>
#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];
ppi sedg[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 (de[0][v.fst] > lim) break;
		if (v.snd != p)
		{
			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;}
		}
	}
}

inline bool comp(const pii &l, const pii &r)
{
	return make_pair(de[0][l.fst], l) < make_pair(de[0][r.fst], r);
}

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];
	}
	for (int i = 0; i < n; i++) {sort(adj[i].begin(), adj[i].end(), comp);}
	ll L = dst[0][n - 1], R = dst[0][n - 1] + 1000000000;
	while (L < R)
	{
		int M = L + R >> 1; idx = 0; lim = 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);
	fastIO :: charOutput('\n');
	return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Incorrect 6 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Incorrect 6 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 708 ms 42832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 688 ms 43308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2077 ms 51028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2077 ms 51028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Incorrect 6 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -