Submission #1041311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041311		HD1	Stations (IOI20_stations)	C++14	5 / 100	558 ms	48560 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
#define ss second
#define all(s) s.begin(),s.end()
#define sz(s) ll(s.size())
#define pb push_back
typedef long long ll;
const ll MAX=1e6;
using namespace std;
ll marc=1, q;
vector<ll> gfo[MAX];
ll m[MAX];
bool vst[MAX];
void dfs(int u, int f){
	m[u]=marc;
	//cout<<u<<'.'<<m[u]<<' ';
	for(auto v:gfo[u]){
		if(v!=f){
			marc+=q;
			dfs(v,u);
		}
	}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
	vector<int> labels(n);
	for(int i=0; i<sz(u); i++){
		gfo[u[i]].pb(v[i]);
		gfo[v[i]].pb(u[i]);
	}
	bool xd=false;
	for(int i=0; i<n; i++){
		if(sz(gfo[i])>2){
			cout<<i<<'\n';
			q=sz(gfo[i]);
			m[i]=0;
			for(int j=0; j<sz(gfo[i]); j++){
				int v=gfo[i][j];
				marc=j+1;
				dfs(v, i);
				cout<<'\n';
			}
			xd=true;
			break;
		}
	}
	if(!xd){
		marc=1;
		q=1;
		for(int i=0; i<n; i++){
			if(sz(gfo[i])==1 && m[i]==0) dfs(i, i);
		}
		
	}
	for(int i=0; i<n; i++){
		labels[i]=m[i];
		m[i]=0;
		gfo[i].clear();
	}
	return labels;
}
int find_next_station(int s, int t, vector<int> c){
	sort(all(c));
	// cout<<s<<' '<<t<<' '<<' ';
	// for(auto x:c){
	// 	cout<<x<<' ';
	// }
	// cout<<'\n';
	ll md=abs(c[sz(c)-1]-s);
	if(s==0 || t==0){
		if(s==0){
			for(auto x:c){
				if(x%md==t%md){
					return x;
				}
			}
		}
		return c[0];
	}
	if(s%md != t%md){
		return c[0];
	}
	if(t>s){
		return c[sz(c)-1];
	}
	return c[0];
}

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