| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053983 | nightfal | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #include "stations.h"
#include <cstdio>
#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
template <typename T> void print(T elem) {cout << elem << " ";}
template <typename T> void print(vector<T> &v) {for(auto elem: v) print(elem); cout << endl;};
template <typename T> void print(vector<vector<T>> &v) {for(auto elem: v) print(elem); cout << endl;};
bool subtask1(vector<vector<int>> &g) {
int n = g.size();
for(auto elem: g)
if (elem.size() > 2) return false;
if (k==1'000) return true;
else return false;
}
bool subtask2(vector<int> &u, vector<int> &v) {
int m = u.size();
for(int i=0; i<m; i++)
if (!(u[i]==i+1 && v[i]==i/2 || u[i]==i/2 && v[i]==i+1))
return false;
if (k==1'000) return true;
else return false;
}
bool subtask3(vector<vector<int>> &g) {
int n=g.size(), cnt=0;
for(auto elem: g)
if(elem.size()>2) cnt++;
if (cnt==1 && k==1'000'000) return true;
return false;
}
bool subtask4(int n, int k) {
if (n<=8 && k==1'000'000'000) return true;
else return false;
}
void genLabels(int key, int node, vector<int> &labels, vector<vector<int>> &g) {
labels[node]=key*1000+1;
for(int i=2; i<1000; i++) {
bool terminal = true;
for(int next: g[node]) {
if(labels[next]==-1) {labels[next] = 1000*key+i; node = next; terminal=false;}
}
if (terminal) return;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n,-1);
vector<vector<int>> g(n);
for (int i=0; i<n-1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
if (subtask3(g)) {
int root = 0;
for(int i=0; i<n; i++)
if(g[i].size() > 2) {root = i; break;}
labels[root] = 1000;
for(int i=0; i<g[root].size(); i++) {
int child = g[root][i];
genLabels(i+1, child, labels, g);
}
}
else if (subtask1(g)) {
int node = 0;
for (int i=0; i<n; i++)
if(g[i].size()==1) node = i;
int prev = node;
for (int i=0; i<n; i++) {
labels[node] = i;
for(int next: g[node])
if(labels[next]== -1) {node = next;}
}
}
// else if (subtask4(n,k)) {
// }
else if (subtask2(u,v)) {
for(int i=0; i<n; i++)
labels[i] = i;
}
// print(labels);
return labels;
}
bool ancestor(int s, int t) {
if (s==0) return true;
while (t) {
if (s==t) return true;
t = (t-1)>>1;
}
return false;
}
int find_next_station(int s, int t, std::vector<int> c) {
int subtask = 0;
if (s>1'000'000 || t>1'000'000) subtask=4;
else if (s>1000 || t>1000) subtask=3;
else {
if (s==0) {
if (c.size()==1) subtask = 1;
else if (c.size()==2) subtask = 2;
}
else if (s==1) {
if (t==0) return 0;
else {
subtask = 2;
for(int elem: c)
if(elem == 2) {subtask=1; break;}
}
}
else {
subtask = 1;
for(int i=0; i<c.size(); i++)
if(!(c[i]==s-1 || c[i]==s+1)) {subtask = 2; break;}
}
}
if (subtask==1) {
for(int next: c)
if (s<t && s<next) return next;
else if (s>t && s>next) return next;
}
else if (subtask==2) {
if (ancestor(2*s+1,t)) return 2*s+1;
else if (ancestor(2*s+2,t)) return 2*s+2;
else return (s-1)/2;
}
else if (subtask==3) {
if (s==1000) return (t/1000)*1000+1;
if (s/1000 == t/1000) {
if (s<t) return s+1;
else return s-1;
}
else {
if (s%1000==1) return 1000;
else return s-1;
}
}
}