oj.uz

Submission #424089

# Submission time Handle Problem Language Result Execution time Memory
424089 2021-06-11T16:29:42 Z lakshith_ Stations (IOI20_stations) C++14
21 / 100
 1119 ms 740 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

#define what_is(a) cout << #a << " is " << a << "\n"
#define checker(a) cout <"checker reached " << a << "\n"
#define ll long long

vector<vector<int>> adj(1000,vector<int>());

vector<int> lbl;

void dfs(int u,int p,int d){
	lbl[u]=d++;
	for(int v:adj[u])
		if(v!=p)
			dfs(v,u,d);
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	lbl = vector<int>(n);
	for(int i=0;i<n;i++)
		adj[i] = vector<int>();
	for(int i=0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	int src = -1;
	for(int i=0;i<n;i++)
		if(adj[i].size()>2)src = i;
	if(src==-1)
		for(int i=0;i<n;i++)
			if(adj[i].size()==1)src = i;
	lbl[src]=0;
	int d = 1;
	for(int a:adj[src]){
			dfs(a,src,d);
			d+=1000;
	}
	return lbl;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(t==0)return c[0];
	if(s==0)return ((ll)t/1000LL)*1000LL + 1LL;
	if(s/1000==t/1000){
		if(s<t)return c[1];
		else return c[0];
	}else{
		return c[0];
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 528 KB Output is correct
2 Correct 592 ms 528 KB Output is correct
3 Correct 1119 ms 512 KB Output is correct
4 Correct 775 ms 512 KB Output is correct
5 Correct 620 ms 504 KB Output is correct
6 Correct 554 ms 648 KB Output is correct
7 Correct 480 ms 556 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 292 KB Invalid labels (duplicates values). scenario=0, label=10
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 528 KB Output is correct
2 Correct 517 ms 504 KB Output is correct
3 Correct 1091 ms 400 KB Output is correct
4 Correct 785 ms 400 KB Output is correct
5 Correct 649 ms 512 KB Output is correct
6 Correct 499 ms 512 KB Output is correct
7 Correct 508 ms 508 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 633 ms 512 KB Output is correct
12 Correct 528 ms 740 KB Output is correct
13 Correct 574 ms 624 KB Output is correct
14 Correct 532 ms 640 KB Output is correct
15 Correct 57 ms 400 KB Output is correct
16 Correct 83 ms 548 KB Output is correct
17 Correct 113 ms 532 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 400 KB Output is correct
2 Correct 759 ms 400 KB Output is correct
3 Correct 661 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 476 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 702 ms 400 KB Output is correct
8 Correct 1031 ms 508 KB Output is correct
9 Correct 688 ms 400 KB Output is correct
10 Correct 622 ms 528 KB Output is correct
11 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=2
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 508 KB Output is correct
2 Correct 484 ms 528 KB Output is correct
3 Correct 1029 ms 552 KB Output is correct
4 Correct 869 ms 400 KB Output is correct
5 Correct 866 ms 512 KB Output is correct
6 Correct 517 ms 528 KB Output is correct
7 Correct 465 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 1 ms 480 KB Output is correct
11 Incorrect 5 ms 328 KB Invalid labels (duplicates values). scenario=0, label=10
12 Halted 0 ms 0 KB -