oj.uz

Submission #226071

# Submission time Handle Problem Language Result Execution time Memory
226071 2020-04-22T13:02:06 Z cfalas Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 36 ms 48128 KB 
#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
#define ll long long
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

int dist[1000000];
int par[1000000];
vector<vii> adj;
#define INF 1500000000
bool vis[1000000];
int o[1000000];
map<int, bool> child[1000000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	adj.assign(n+1, vii());
	for(int i=0;i<m;i++){
		adj[r[i][0]].push_back(ii(l[i], r[i][1]));
		adj[r[i][1]].push_back(ii(l[i], r[i][0]));
		child[r[i][1]][r[i][0]] = true;
		child[r[i][0]][r[i][1]] = true;
	}
	for(int i=0;i<n;i++){
		sort(adj[i].begin(), adj[i].end());
	}
	priority_queue<ii> q;
	q.push(ii(0, 0));
	dist[0] = 0;
	for(int i=1;i<n;i++) dist[i]=INF;

	while(!q.empty()){
		ii t = q.top();
		q.pop();

		if(-t.F>dist[t.S]) continue;
		//cout<<t.F<<" "<<t.S<<" "<<dist[t.S]<<endl;
		for(auto v : adj[t.S]){
			if(dist[v.S]> -t.F + v.F){
				dist[v.S] = v.F - t.F;
				par[v.S] = t.S;
				q.push(ii(-dist[v.S], v.S));

			}
		}
	}
	vii d;
	for(int i=0;i<k;i++){
		d.push_back(ii(-dist[p[i]], p[i]));
	}
	for(int i=0;i<n;i++){
		if(i) o[i]++;
		o[par[i]]++;
	}
	sort(d.begin(), d.end());
	for(auto x : d){
		//cout<<x.S<<" "<<x.F<<endl;
		int t = x.S;
		bool found = false;
		while(par[t]!=t){
			//cout<<t<<" ";
			if(child[par[t]][t]==false){found=true;break;}
			else if(o[par[t]]>3){ child[par[t]][t]=false, o[par[t]]--; found = true; break;}
			t = par[t];
		}
		//cout<<endl;
		if(!found) return -x.F;
	}
	return -1;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 30 ms 47360 KB Output is correct
3 Correct 30 ms 47352 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 36 ms 47616 KB Output is correct
6 Correct 31 ms 47480 KB Output is correct
7 Correct 31 ms 47616 KB Output is correct
8 Correct 31 ms 47616 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 30 ms 47360 KB Output is correct
3 Correct 30 ms 47352 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 36 ms 47616 KB Output is correct
6 Correct 31 ms 47480 KB Output is correct
7 Correct 31 ms 47616 KB Output is correct
8 Correct 31 ms 47616 KB Output is correct
9 Incorrect 34 ms 48128 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47352 KB Output is correct
2 Correct 30 ms 47360 KB Output is correct
3 Correct 30 ms 47352 KB Output is correct
4 Correct 32 ms 47616 KB Output is correct
5 Correct 36 ms 47616 KB Output is correct
6 Correct 31 ms 47480 KB Output is correct
7 Correct 31 ms 47616 KB Output is correct
8 Correct 31 ms 47616 KB Output is correct
9 Incorrect 34 ms 48128 KB Output isn't correct
10 Halted 0 ms 0 KB -