oj.uz

Submission #377830

# Submission time Handle Problem Language Result Execution time Memory
377830 2021-03-15T08:16:31 Z autumn_eel Stations (IOI20_stations) C++14
10 / 100
 986 ms 1060 KB 
#include "stations.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;

static vector<vector<int>>E;
static vector<int>labels;
static int cnt=0;

void dfs(int v,int p){
	int x=0;
	int d=0;
	for(int u:E[v]){
		if(u==p)continue;
		dfs(u,v);
		x|=labels[u];
		d++;
	}
	if(d<=1){
		x|=1<<cnt;
		cnt++;
	}
	labels[v]=x;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
	E=vector<vector<int>>(n);
	labels=vector<int>(n);
	cnt=0;
	vector<int>deg(n);
	rep(i,n-1){
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
		deg[u[i]]++;
		deg[v[i]]++;
	}
	dfs(0,-1);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for(int u:c){
		if((s|u)==u)continue;
		if((t|u)==u)return u;
	}
	for(int u:c){
		if((s|u)==u)return u;
	}
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 524 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=0, label=-1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 484 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=-1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 492 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=0, label=-1
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 892 KB Output is correct
2 Correct 928 ms 764 KB Output is correct
3 Correct 691 ms 756 KB Output is correct
4 Correct 3 ms 756 KB Output is correct
5 Correct 5 ms 756 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 679 ms 756 KB Output is correct
8 Correct 986 ms 756 KB Output is correct
9 Correct 783 ms 868 KB Output is correct
10 Correct 620 ms 756 KB Output is correct
11 Correct 6 ms 736 KB Output is correct
12 Correct 7 ms 756 KB Output is correct
13 Correct 5 ms 868 KB Output is correct
14 Correct 5 ms 764 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 551 ms 736 KB Output is correct
17 Correct 544 ms 1060 KB Output is correct
18 Correct 511 ms 1012 KB Output is correct
19 Correct 569 ms 736 KB Output is correct
20 Correct 508 ms 756 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Invalid labels (values out of range). scenario=1, k=1000000000, vertex=0, label=-1
2 Halted 0 ms 0 KB -