oj.uz

Submission #1054759

# Submission time Handle Problem Language Result Execution time Memory
1054759 2024-08-12T11:58:49 Z LittleOrange Stations (IOI20_stations) C++17
16 / 100
 481 ms 948 KB 
#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<ll> labels(n);
	iota(labels.begin(),labels.end(),0);
	vector<vector<ll>> con(n);
	for(ll i = 0;i<n-1;i++){
		con[u[i]].push_back(v[i]);
		con[v[i]].push_back(u[i]);
	}
	fill(labels.begin(),labels.end(),-1);
	/*for(ll i = 0;i<n;i++){
		if (con[i].size()==1&&labels[i]==-1){
			ll cur = i;
			ll it = 0;
			while(cur!=-1){
				labels[cur] = it++;
				ll nxt = -1;
				for(ll j : con[cur]) if (labels[j]==-1) nxt = j;
				cur = nxt;
			}
		}
	}*/
	ll rt = 0;
	for(ll i = 0;i<n;i++) if(con[i].size()>2) rt = i;
	labels[rt] = 0;
	ll gp = 0;
	for(ll i : con[rt]){
		ll g = (++gp)*1000;
		ll x = i;
		while(x!=-1){
			labels[x] = g++;
			ll nw = -1;
			for(ll j : con[x]){
				if(labels[j]==-1){
					nw = j;
				}
			}
			x = nw;
		}
	}
	//for(ll i = 0;i<n;i++) cerr << labels[i] << " \n"[i+1==n];
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	//cerr << s << " " << t << " :";
	//for(ll i : c) cerr << " " << i;
	//cerr << "\n";
	/*s++;t++;
	ll lgs = __lg(s), lgt = __lg(t);
	if (lgs<lgt){
		ll x = t>>(lgt-lgs);
		if (s==x){
			return (t>>(lgt-lgs-1))-1;
		}
	}
	return (s>>1)-1;*/
	/*if (t>s) return s+1;
	else return s-1;*/
	ll gs = s/1000;
	ll gt = t/1000;
	if (gs==0){
		for(ll i : c){
			if (i/1000==gt) return i;
		}
	}else if(gs==gt){
		if(s>t){
			for(ll i : c){
				if (i<s) return i;
			}
		}else{
			for(ll i : c){
				if (i>s) return i;
			}
		}
	}else{
		for(ll i : c){
			if (i<s) return i;
		}
	}
	return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 776 KB Output is correct
2 Correct 237 ms 684 KB Output is correct
3 Correct 411 ms 684 KB Output is correct
4 Correct 292 ms 696 KB Output is correct
5 Correct 283 ms 768 KB Output is correct
6 Correct 207 ms 768 KB Output is correct
7 Correct 231 ms 772 KB Output is correct
8 Correct 0 ms 768 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 278 ms 684 KB Output is correct
12 Correct 227 ms 768 KB Output is correct
13 Correct 287 ms 760 KB Output is correct
14 Correct 248 ms 684 KB Output is correct
15 Correct 43 ms 764 KB Output is correct
16 Correct 32 ms 824 KB Output is correct
17 Correct 61 ms 816 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 684 KB Output is correct
2 Correct 320 ms 772 KB Output is correct
3 Correct 294 ms 772 KB Output is correct
4 Correct 1 ms 948 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 948 KB Output is correct
7 Correct 321 ms 684 KB Output is correct
8 Correct 471 ms 840 KB Output is correct
9 Correct 339 ms 684 KB Output is correct
10 Correct 326 ms 684 KB Output is correct
11 Incorrect 1 ms 344 KB Invalid labels (values out of range). scenario=5, k=1000000000, vertex=0, label=-1
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 314 ms 684 KB Partially correct
2 Partially correct 255 ms 684 KB Partially correct
3 Correct 481 ms 684 KB Output is correct
4 Partially correct 365 ms 684 KB Partially correct
5 Partially correct 306 ms 684 KB Partially correct
6 Partially correct 255 ms 684 KB Partially correct
7 Partially correct 270 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 1 ms 776 KB Partially correct
10 Partially correct 0 ms 772 KB Partially correct
11 Incorrect 2 ms 432 KB Invalid labels (values out of range). scenario=0, k=1000000000, vertex=0, label=-1
12 Halted 0 ms 0 KB -