oj.uz

Submission #301794

# Submission time Handle Problem Language Result Execution time Memory
301794 2020-09-18T08:16:00 Z Nodir_Bobiev Aesthetic (NOI20_aesthetic) C++17
22 / 100
 2000 ms 31132 KB 
/*
+----------------------------------------------------------------+
| In the name of Allah, the most Gracious and the most Merciful. |
+----------------------------------------------------------------+
+------------------------------------------------------+
| Ба номи Худованди беандоза Mеҳрабон ва ниҳоят Бораҳм |
+------------------------------------------------------+
+-----------------------------------------+
| Во имя Аллаха Милостивого, Милосердного |
+-----------------------------------------+
This world is a trial for us
And we know well that we must
Obey the orders from my lord
To avoid all sins and seek reward
*/
# include <bits/stdc++.h>
# define FILE
using namespace std;

const int N = 3e5 + 100;
const long long inf = 1e15;

int n, m, timm, curr, bridge, U[N], V[N], W[N], maxW[N], tin[N], low[N];
long long dist[2][N], within[N], without[N];
vector < int > graph[N];

void bfs( int v, long long *dist ){
	for( int i = 1; i <= n; i ++ ) dist[i] = inf;
	dist[v] = 0;
	priority_queue < pair < long long, int > > pq;
	pq.push({0,v});
	while( !pq.empty() ){
		long long  dst; int v; tie(dst, v) = pq.top(); pq.pop();
		if( dst > dist[v] )continue;
		for( auto i: graph[v] ){
			int to = (v == V[i]?U[i]:V[i]);
			if( dist[to] > dist[v] + W[i] ){
				dist[to] = dist[v] + W[i];
				pq.push({dist[to], to});
			}
		}
	}
}
void dfs( int v, int f, int ras ){
	tin[v] = low[v] = ++timm;
	for( auto i: graph[v] ){
		if( without[i] > ras )continue;
		int to = (v==V[i]?U[i]:V[i]);
		if( tin[to] <= curr ){
			dfs(to, v, ras);
			if( low[to] > tin[v] && tin[n] > tin[to] && within[i] > ras )
				bridge = 1;
			low[v] = min( low[v], low[to]);
		}else if( to != f ){
			low[v] = min( low[v], tin[to]);
		}
	}
}

bool check( long long ras){
	curr = timm;
	bridge = 0;
	dfs(1, 0, ras);
	//cout << "check " << curr << ' ' << tin[n] << ' ' <<bridge << endl;
	if( tin[n] <= curr) return 0;
	if( bridge )return 0;
	return true;
}

int main(){
    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for( int i = 1; i <= m; i ++ ){
    	cin >> V[i] >> U[i] >> W[i];
    	graph[V[i]].push_back( i );
    	graph[U[i]].push_back( i );
    }
    for( int i = m-1; i >= 1; i -- ){
    	maxW[i] = max( W[i], maxW[i+1]);
    }
    bfs( 1, dist[0]);
    bfs( n, dist[1]);
    for( int i = 1; i <= m; i ++ ){
    	without[i] = min( dist[0][V[i]] + dist[1][U[i]], dist[0][U[i]] + dist[1][V[i]]) + W[i];
    	within[i] = without[i] + maxW[i];
    }
    /*
    for( int i = 1; i <= m; i ++ ){
    	cout << V[i] <<' ' << U[i] << ' ' << without[i] << ' ' << within[i] << endl;
    }cout << endl;
    */
    long long l = dist[0][n]-1, r = dist[0][n] + maxW[1];
    while( r - l > 1 ){
    	long long mid = ( l + r ) >> 1;
    	//cout << l << ' '<< mid << ' ' << r << endl;
    	if( check(mid) )
    		r = mid;
    	else 
    		l = mid;
    }
    cout << r;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 30456 KB Output is correct
2 Correct 536 ms 30712 KB Output is correct
3 Correct 532 ms 30456 KB Output is correct
4 Correct 535 ms 30456 KB Output is correct
5 Correct 544 ms 30332 KB Output is correct
6 Correct 574 ms 30840 KB Output is correct
7 Correct 555 ms 30840 KB Output is correct
8 Correct 556 ms 31096 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 31132 KB Output is correct
2 Correct 678 ms 30728 KB Output is correct
3 Correct 588 ms 30712 KB Output is correct
4 Correct 608 ms 30968 KB Output is correct
5 Correct 640 ms 30420 KB Output is correct
6 Correct 587 ms 30560 KB Output is correct
7 Correct 627 ms 30424 KB Output is correct
8 Correct 703 ms 30712 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 22128 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 2029 ms 22128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Incorrect 5 ms 7424 KB Output isn't correct
3 Halted 0 ms 0 KB -