oj.uz

답안 #431970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431970 2021-06-17T17:50:49 Z gonengazit 기지국 (IOI20_stations) C++14
0 / 100
 884 ms 528 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;
// 	}
// }

void dfs1(int i, int f=0){
	int tin=++tme;
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i);
		}
	}
	int tout=tme;
	labels[i]=tin*1000+tout;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	// for(int i=0; i<n; i++){
	// 	labels[i]=i;
	// }
	//return labels;
	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]);
	}
	int curr;
	for(int i=0; i<n; i++){
		if(g[i].size()==1){
			curr=i;
		}
	}


	int i=0;
	do{
		labels[curr]=i++;
		if(labels[g[curr][0]]==-1){
			curr=g[curr][0];
		}
		else{
			curr=g[curr][1];
		}
	}while(g[curr].size()>1);
	labels[curr]=i;
	return labels;

	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) {
	
	if(t>s){
		return c[0];
	}
	else{
		return c[1];
	}

	
	// int tin=t/1000;
	// int tout=t%1000;

	// int sin=s/1000;
	// int sout=s%1000;

	// int f;
	// for(auto i:c){
	// 	int in=i/1000;
	// 	int out=i%1000;
	// 	if(in<sin){
	// 		f=i;
	// 		continue;
	// 	}
	// 	if (tin>=in&&tout<=out){
	// 		return i;
	// 	}
	// }
	// return f;


	// 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
3
0 1 2
1 2 2
1 4 2*/

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:59:14: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |   labels[curr]=i++;
      |              ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 579 ms 492 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 280 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=4, label=-1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 567 ms 520 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 884 ms 488 KB Output is correct
2 Incorrect 653 ms 400 KB Wrong query response.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 545 ms 528 KB Wrong query response.
2 Halted 0 ms 0 KB -