oj.uz

Submission #431838

# Submission time Handle Problem Language Result Execution time Memory
431838 2021-06-17T15:57:31 Z gonengazit Stations (IOI20_stations) C++14
0 / 100
 907 ms 656 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0, int s=0){
	int tin=++tme;
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i,(t+1)%2,(s+1)%3);
		}
	}
	int tout=tme;
	if(t==0){
		labels[i]=6*tin+3*t+s;
	}
	else{
		labels[i]=6*(tin+tout)+3*t+s;
	}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	g.assign(n,vector<int>());
	for(int i=0; i<n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs1(0);
	return labels;
}

ii get(int x){
	return ii(x/3%2,x%3);
}
int find_next_station(int s, int t, std::vector<int> c) {

	ii r=get(s);
	s/=6;
	vector<pair<ii,int>> cld;
	int f=-1;
	if(r.x==0){
		int prev=s;
		for(auto i:c){
			if(get(i).y!=(r.y+1)%3){
				f=i;
				continue;
			}
			int k=i/6;
			cld.emplace_back(ii(prev+1,k-(prev+1)),i);
			prev=k-(prev+1);
		}
	}
	else{
		for(auto i:c){
			if(get(i).y!=(r.y+1)%3){
				f=i;
				continue;
			}
			if(!cld.empty())
				cld.back().x.y=i/6-1;
			cld.emplace_back(ii(i/6,-1),i);
		}
		if(!cld.empty()){
			cld.back().x.y=s-(cld[0].x.x-1);
		}
	}

	ii h=get(t);
	t/=6;

	for(auto i:cld){
		if(h.x==0&&i.x.x<=t&&i.x.y>=t){
			return i.y;
		}
		else if(h.x==1&&2*i.x.x<=t&&2*i.x.y>=t){
			return i.y;
		}
	}
	return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
1
1 4 2*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 551 ms 632 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 400 KB Output is correct
2 Correct 686 ms 508 KB Output is correct
3 Correct 560 ms 556 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Incorrect 4 ms 476 KB Wrong query response.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 546 ms 656 KB Wrong query response.
2 Halted 0 ms 0 KB -