Submission #1059484

#TimeUsernameProblemLanguageResultExecution timeMemory
1059484nightfalStations (IOI20_stations)C++17
62.68 / 100
653 ms1196 KiB
// #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,9)) return n<=8? 4:5; if (k==pow(10,9)) return 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) { 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(int n, vector<vector<int>> &g, vector<int> &labels) { int preNum=0, postNum=0, dNum=0; vector<int> pre(n,-1), post(n,-1), dist(n,-1); pporder(0,preNum,postNum,dNum,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] = pre[i]*1'000+post[i]; labels[i] = pre[i]*1'000+post[i]+pow(10,6); // labels[i] = dist[i]%2? pre[i]+1000: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(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>pow(10,6) || t>pow(10,6)) 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(int s, int t, vector<int> &c) { s %= (int) pow(10,6), t %= (int) pow(10,6); 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++) { int temp = c[i] % (int) pow(10,6); pre[i] = temp/1'000; post[i] = temp%1'000; } // cout << "pre: "; print(pre); // cout << "post: "; print(post); if(preS < pre[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 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(s,t,c); } }

Compilation message (stderr)

stations.cpp: In function 'void labelsSubtask3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  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:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     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:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0; i<g[0].size(); i++) {
      |               ~^~~~~~~~~~~~
stations.cpp: In function 'int decideFindSubtask(int, int, std::vector<int>&)':
stations.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    for(int i=0; i<c.size(); i++)
      |                 ~^~~~~~~~~
stations.cpp: In function 'int findSubtask5(int, int, std::vector<int>&)':
stations.cpp:187:22: warning: unused variable 'postS' [-Wunused-variable]
  187 |  int preS = s/1'000, postS = s%1'000;
      |                      ^~~~~
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:109:28: warning: control reaches end of non-void function [-Wreturn-type]
  109 |     vector<vector<int>> g(n);
      |                            ^
stations.cpp: In function 'int findSubtask1(int, int, std::vector<int>&)':
stations.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^
stations.cpp: In function 'int findSubtask5(int, int, std::vector<int>&)':
stations.cpp:190:19: warning: control reaches end of non-void function [-Wreturn-type]
  190 |  vector<int> pre(m), post(m);
      |                   ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
  218 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...