oj.uz

Submission #235685

# Submission time Handle Problem Language Result Execution time Memory
235685 2020-05-29T11:13:47 Z Dilshod_Imomov Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 8 ms 3072 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
const int NN = 1e5 + 7;
 
vector < pair < int, int > > adj[NN];
int dp[NN], l[NN], used[NN], isExit[NN], ban[NN];
 
void dfs( int v, int p ) {
	int mn1 = 1e9, mn2 = 1e9;
	used[v] = 1;
	if ( isExit[v] ) {
		dp[v] = 0;
		return;
	}
	// cout << "-> " << v << ' ' << p << '\n';
	for ( auto pr: adj[v] ) {
		int u = pr.first, ind = pr.second;
		if ( ban[u] ) {
			continue;
		}
		if ( !used[u] ) {
			dfs( u, v );
		}
		if ( u != p ) {
			int cnt = dp[u] + l[ind];
			if ( cnt <= mn1 ) {
				mn2 = mn1;
				mn1 = cnt;
			}
			else if ( cnt < mn2 ) {
				mn2 = cnt;
			}
		}
	}
 
	// cout << "-> " << v << ' ' << mn1 << ' ' << mn2 << '\n';
	dp[v] = mn2;
}
 
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for ( int i = 0; i < m; i++ ) {
		int u = R[i][0], v = R[i][1];
		adj[u].push_back( { v, i } );
		adj[v].push_back( { u, i } );
		l[i] = L[i];
	}
	for ( int i = 0; i < K; i++ ) {
		isExit[ P[i] ] = 1;
	}
	for ( int i = 0; i < n; i++ ) {
		if ( (int)adj[i].size() == 2 && i && !isExit[i] ) {
			ban[i] = 1;
		}
	}
	dfs( 0, 0 );
	return dp[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Incorrect 8 ms 3072 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Incorrect 8 ms 3072 KB Output isn't correct
10 Halted 0 ms 0 KB -