// #include "stations.h"
#include <cstdio>
#include <iostream>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <tuple>
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;};
int DecideLabelsSubtask(int n, int k, vector<vector<int>> &g, vector<int> &u, vector<int> &v) {
if (k>=pow(10,6)) return 5;
// if (k==pow(10,9)) return n<=8? 4:5;
else if (k>pow(10,3)) return 3;
for(auto elem: g)
if(elem.size()>2) return 2;
return 1;
}
void labelsSubtask1(int n, vector<vector<int>> &g, vector<int> &labels) {
int node = 0;
for (int i=0; i<n; i++)
if(g[i].size()==1) node = i;
for (int i=0; i<n; i++) {
labels[node] = i;
for(int child: g[node])
if(labels[child]== -1) {node = child;}
}
return;
}
void labelsSubtask2(int n, vector<vector<int>> &g, vector<int> &labels) {
for(int i=0; i<n; i++)
labels[i] = i;
return;
}
void genLabels3(int key, int node, vector<vector<int>> &g, vector<int> &labels) {
labels[node]=key*1000+1;
for(int i=2; i<1000; i++) {
bool terminal = true;
for(int child: g[node]) {
if(labels[child]==-1) {labels[child] = 1000*key+i; node = child; terminal=false;}
}
if (terminal) return;
}
}
void labelsSubtask3(int n, vector<vector<int>> &g, vector<int> &labels) {
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];
genLabels3(i+1, child, g, labels);
}
return;
}
void genLabels4(int base, int key, int exp, int node, vector<vector<int>> &g, vector<int> &labels) {
labels[node]=base + key*pow(10,exp);
base = labels[node];
for(int i=0; i<g[node].size(); i++) {
int child = g[node][i];
if (labels[child]==-1)
genLabels4(base,i+1,exp-1, child, g, labels);
}
return;
}
void labelsSubtask4(int n, vector<vector<int>> &g, vector<int> &labels) {
labels[0] = pow(10,8);
int base = labels[0];
for(int i=0; i<g[0].size(); i++) {
int child = g[0][i];
if (labels[child]==-1)
genLabels4(base,i+1,7, child, g, labels);
}
}
pair<int,int> pporder(int node, int preNum, int postNum, int dNum, vector<vector<int>> &g,
vector<int> &pre, vector<int> &post, vector<int> &dist) {
if (pre[node]!=-1) return {preNum,postNum};
pre[node] = preNum++;
dist[node] = dNum++;
for(int child: g[node])
// if (pre[child]==-1)
tie(preNum, postNum) = pporder(child,preNum,postNum,dNum,g,pre,post,dist);
post[node] = postNum++;
return {preNum,postNum};
}
void labelsSubtask5_65(int n, vector<vector<int>> &g, vector<int> &labels) {
vector<int> pre(n,-1), post(n,-1), dist(n,-1);
pporder(0,0,0,0,g,pre,post,dist);
for(int i=0; i<n; i++)
labels[i] = pre[i]*1'000+post[i];
}
int dfs(int node, int orderNum, int dNum, vector<vector<int>> &g,
vector<int> &pre, vector<int> &post, vector<int> &dist) {
if (pre[node]!=-1) return orderNum;
pre[node] = orderNum++;
dist[node] = dNum++;
for(int child: g[node])
// if (pre[child]==-1)
orderNum = dfs(child,orderNum,dNum,g,pre,post,dist);
post[node] = orderNum++;
return orderNum;
}
void labelsSubtask5_90(int n, vector<vector<int>> &g, vector<int> &labels) {
vector<int> pre(n,-1), post(n,-1), dist(n,-1);
dfs(0,0,0,g,pre,post,dist);
// cout << "pre: "; print(pre);
// cout << "post: "; print(post);
// cout << "dist: "; print(dist);
for(int i=0; i<n; i++)
labels[i] = dist[i]%2? pre[i]+2'000:post[i];
// cout << "labels: "; print(labels);
}
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]);
}
int subtask = DecideLabelsSubtask(n,k,g,u,v);
switch(subtask) {
case 1: labelsSubtask1(n,g,labels); return labels;
case 2: labelsSubtask2(n,g,labels); return labels;
case 3: labelsSubtask3(n,g,labels); return labels;
case 4: labelsSubtask4(n,g,labels); return labels;
case 5: labelsSubtask5_90(n,g,labels); return labels;
// case 5: labelsSubtask5_65(n,g,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 decideFindSubtask(int s, int t, vector<int> &c) {
// if (s>pow(10,8) || t>pow(10,8)) return 4;
if (s>2*pow(10,3) || c[0]>2*pow(10,3)) return 5;
else if (s>pow(10,3) || t>pow(10,3)) return 3;
switch(s) {
case 0:
if (c.size()==1) return 1;
else if (c.size()==2) return 2;
case 1:
if (t==0) return -1;
else {
for(int elem: c)
if(elem > 2) return 2;
return 1;
}
default:
for(int i=0; i<c.size(); i++)
if(!(c[i]==s-1 || c[i]==s+1)) return 2;
return 1;
}
}
int findSubtask1(int s, int t, vector<int> &c) {
for(int child: c)
if (s<t && s<child) return child;
else if (s>t && s>child) return child;
}
int findSubtask2(int s, int t, vector<int> &c) {
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;
}
int findSubtask3(int s, int t, vector<int> &c) {
if (s==1000) return (t/1000)*1000+1;
else 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;
}
}
int findSubtask4(int s, int t, vector<int> &c) {
int sZeros=0, tZeros=0, s2=s, t2=t;
while (s2%10==0) {s2/=10; sZeros++;}
while (t2%10==0) {t2/=10; tZeros++;}
if(sZeros>tZeros) {
for(int i=0; i<sZeros-tZeros; i++) t2/=10;
int divisor = pow(10,sZeros-1);
if (s2==t2) {return (t/divisor)*divisor;}
}
int divisor = pow(10,sZeros+1);
return (s/divisor)*divisor;
}
int findSubtask5_65(int s, int t, vector<int> &c) {
int preS = s/1'000, postS = s%1'000;
int preT = t/1'000, postT = t%1'000;
int m = c.size();
vector<int> pre(m), post(m);
for(int i=0; i<m; i++) {
pre[i] = c[i]/1'000; post[i] = c[i]%1'000;
}
if(preS == 0) { // s is the root.
for(int i=0; i<m; i++)
if(postT<=post[i]) return c[i];
}
else { // s is an intermediate node.
if(preT < preS) return c[0];
for(int i=1; i<m; i++)
if(postT<=post[i]) return c[i];
return c[0];
}
}
int findSubtask5_90(int s, int t, vector<int> &c) {
int m = c.size();
vector<int> pre(m,-1), post(m,-1);
// cout << "s:" << s << " t:" << t << endl;
// cout << "c: "; print(c);
if (s>=2000) { // s is preordered and c[i] is postordered.
s -= 2000;
for(int i=0; i<m; i++)
post[i] = c[i];
if (t>=2000) t -= 2000;
if(s==0) // s is the root.
for(int i=0; i<m; i++)
if(t<=post[i]) return c[i];
else { // s is an intermediate node.
if (t<s || t>c[m-2]) return c[m-1];
for(int i=0; i<m-1; i++)
if(t<=post[i]) return c[i];
// return c[m-1];
}
}
else { // s is postordered and c[i] is preordered.
for(int i=0; i<m; i++)
pre[i] = c[i]-2000;
if (t>=2000) t -= 2000;
if(s==0) {// s is the root.
for(int i=1; i<m; i++)
if(t<=pre[i]) return c[i-1];
return c[m-1];
}
else { // s is an intermediate node.
if (t<c[1] || t>s) return c[0];
for(int i=2; i<m; i++)
if(t<=pre[i]) return c[i-1];
return c[m-1];
}
}
}
int find_next_station(int s, int t, std::vector<int> c) {
int subtask = decideFindSubtask(s,t,c);
switch(subtask) {
case -1: return 0;
case 1: return findSubtask1(s,t,c);
case 2: return findSubtask2(s,t,c);
case 3: return findSubtask3(s,t,c);
case 4: return findSubtask4(s,t,c);
case 5: return findSubtask5_90(s,t,c);
// case 5: return findSubtask5_65(s,t,c);
}
}
Compilation message
stations.cpp: In function 'void labelsSubtask3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i=0; i<g[root].size(); i++) {
| ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void genLabels4(int, int, int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<g[node].size(); i++) {
| ~^~~~~~~~~~~~~~~
stations.cpp: In function 'void labelsSubtask4(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0; i<g[0].size(); i++) {
| ~^~~~~~~~~~~~
stations.cpp: In function 'int decideFindSubtask(int, int, std::vector<int>&)':
stations.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i=0; i<c.size(); i++)
| ~^~~~~~~~~
stations.cpp: In function 'int findSubtask5_65(int, int, std::vector<int>&)':
stations.cpp:202:22: warning: unused variable 'postS' [-Wunused-variable]
202 | int preS = s/1'000, postS = s%1'000;
| ^~~~~
stations.cpp: In function 'int findSubtask5_90(int, int, std::vector<int>&)':
stations.cpp:231:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
231 | if(s==0) // s is the root.
| ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:123:28: warning: control reaches end of non-void function [-Wreturn-type]
123 | vector<vector<int>> g(n);
| ^
stations.cpp: In function 'int findSubtask1(int, int, std::vector<int>&)':
stations.cpp:172:1: warning: control reaches end of non-void function [-Wreturn-type]
172 | }
| ^
stations.cpp: In function 'int findSubtask5_65(int, int, std::vector<int>&)':
stations.cpp:205:19: warning: control reaches end of non-void function [-Wreturn-type]
205 | vector<int> pre(m), post(m);
| ^
stations.cpp: In function 'int findSubtask5_90(int, int, std::vector<int>&)':
stations.cpp:222:22: warning: control reaches end of non-void function [-Wreturn-type]
222 | vector<int> pre(m,-1), post(m,-1);
| ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:270:1: warning: control reaches end of non-void function [-Wreturn-type]
270 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
347 ms |
684 KB |
Output is correct |
| 2 |
Correct |
324 ms |
684 KB |
Output is correct |
| 3 |
Correct |
632 ms |
684 KB |
Output is correct |
| 4 |
Correct |
388 ms |
684 KB |
Output is correct |
| 5 |
Correct |
353 ms |
776 KB |
Output is correct |
| 6 |
Correct |
263 ms |
772 KB |
Output is correct |
| 7 |
Correct |
276 ms |
772 KB |
Output is correct |
| 8 |
Correct |
1 ms |
768 KB |
Output is correct |
| 9 |
Correct |
3 ms |
768 KB |
Output is correct |
| 10 |
Correct |
0 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
285 ms |
684 KB |
Output is correct |
| 2 |
Correct |
359 ms |
684 KB |
Output is correct |
| 3 |
Correct |
593 ms |
684 KB |
Output is correct |
| 4 |
Correct |
456 ms |
684 KB |
Output is correct |
| 5 |
Correct |
424 ms |
684 KB |
Output is correct |
| 6 |
Correct |
303 ms |
684 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3042 ms |
940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3038 ms |
684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3047 ms |
940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
