Submission #620729

#	Time	Username	Problem	Language	Result	Execution time	Memory
620729		KLPP	Stations (IOI20_stations)	C++14	0 / 100	972 ms	71896 KiB

stations

#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
vector<int> nei[1000000];
int L[1000000];
int R[1000000];
int cnt;
bool visited[1000000];
void DFS(int node){
	visited[node]=true;
	L[node]=cnt;
	cnt++;
	trav(a,nei[node]){
		if(!visited[a]){
			DFS(a);
		}
	}
	R[node]=cnt-1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	rep(i,0,(int)u.size()){
		nei[u[i]].push_back(v[i]);
		nei[v[i]].push_back(u[i]);
	}
	cnt=0;
	rep(i,0,n)visited[i]=false;
	DFS(0);
	vector<int> answer(n);
	rep(i,0,n)answer[i]=R[i]*1000+L[i];
	//rep(i,0,n)cout<<L[i]<<" "<<R[i]<<endl;
	//rep(i,0,n)cout<<answer[i]<<endl;
	return answer;
}
int contain(int a, int b, int c, int d){
	if(a<=c && d<=b)return -1;
	if(c<=a && b<=d)return 1;
	
	return 0;
}
int find_next_station(int s, int t, std::vector<int> c) {
	int sL=s%1000;
	int sR=s/1000;
	int tL=t%1000;
	int tR=t/1000;
	//cout<<sL<<" "<<sR<<" "<<tL<<" "<<tR<<endl;
	//cout<<contain(sL,sR,tL,tR)<<endl;
	if(contain(sL,sR,tL,tR)==0){
		trav(a,c){
			int aL=a%1000;
			int aR=a/1000;
			if(contain(aL,aR,sL,sR)==-1){
				return a;
			}
		}
	}
	if(contain(sL,sR,tL,tR)==-1){
		trav(a,c){
			int aL=a%1000;
			int aR=a/1000;
			//cout<<"A"<<a<<endl;
			//cout<<contain(aL,aR,sL,sR)<<endl;
			if(contain(aL,aR,tL,tR)==-1 && contain(aL,aR,sL,sR)==1){
				//cout<<a<<endl;
				return a;
			}
		}
		
	}
	trav(a,c){
		int aL=a%1000;
		int aR=a/1000;
		if(contain(aL,aR,sL,sR)==-1){
			
			return a;
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61