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 <bits/stdc++.h>
#include "stations.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
vvi g;
vi vis;
vi l;
vi indeg;
int y=-1;
int cont=0;
void dfs1(int u, int p){
// cout<<u<< " ";
vis[u]=true;
if(u==y){
l[u]=1000+l[p];
}else{
l[u]=cont;
cont++;
}
for(auto v: g[u]){
if(!vis[v]){
dfs1(v,u);
}
}
}
void dfs(int u){
vis[u]=true;
l[u]=cont;
cont++;
for(auto v: g[u]){
if(!vis[v]){
dfs(v);
}
}
}
vi label(int n, int k, vi u, vi v) {
l.resize(n,0);
vis.resize(n,0);
indeg.resize(n,0);
g.resize(n, vi());
y=-1;
cont=0;
for(int i=0; i<n-1; i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
indeg[u[i]]++;
indeg[v[i]]++;
}
vi x;
for(int i=n-1; i>=0; i--){
if(indeg[i]==1) x.push_back(i);
if(indeg[i]==3) y=i;
// cout<<x<<y<<endl;
}
if(k>1000 && y!=-1){
int a=g[y][0], b = g[y][1], c=g[y][2];
int x1=-1;
for(int i=0; i<(int)x.size(); i++){
if(x[i]!=a && x[i]!=b && x[i]!=c){
x1=x[i];
}else{
if(x[i]==a) y=a;
if(x[i]==b) y=b;
if(x[i]==c) y=c;
}
}
// cout<<y<<endl;
if(x1==-1){
if(y!=a){
x1=a;
}else{
x1=b;
}
}
dfs1(x1,x1);
}else{
dfs(0);
}
return l;
}
int find_next_station(int s, int t, vi c) {
// return 0;
int size = (int)c.size();
if(size==1)return c[0];
for(int i=0; i<size; i++){
if(c[i]==t) return c[i];
}
if(s<=1000 && t<=1000){
if(t>s){
return c[1];
}else{
return c[0];
}
}else{
if(t-1000>s){
return c[1];
}else{
return c[0];
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |