Submission #1054549

#TimeUsernameProblemLanguageResultExecution timeMemory
1054549nightfalStations (IOI20_stations)C++17
5 / 100
482 ms936 KiB
// #include "stations.h" #include <cstdio> #include <iostream> #include <cassert> #include <map> #include <vector> #include <algorithm> #include <cmath> 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(int k, 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(int k, 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(int k, 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; // } bool DecideLabelsSubtask(int n, int k, vector<vector<int>> &g, vector<int> &u, vector<int> &v) { if (k==pow(10,9)) return 4; else if (k==pow(10,6)) 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<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]; genLabels4(base,i+1,7, child, g, 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); break; case 2: labelsSubtask2(n,labels); break; case 3: labelsSubtask3(n,g,labels); break; case 4: labelsSubtask4(n,g,labels); } // 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; } bool decideFindSubtask(int s, int t, vector<int> &c) { if (s>pow(10,8) || t>pow(10,8)) return 4; else if (s>1'000 || t>1'000) 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 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: for(int child: c) if (s<t && s<child) return child; else if (s>t && s>child) return child; case 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; case 3: 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; } case 4: return 0; } }

Compilation message (stderr)

stations.cpp: In function 'void labelsSubtask3(int, std::vector<std::vector<int> >&, std::vector<int>&)':
stations.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  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:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     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:101:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=0; i<=g[0].size(); i++) {
      |               ~^~~~~~~~~~~~~
stations.cpp: In function 'bool decideFindSubtask(int, int, std::vector<int>&)':
stations.cpp:146:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for(int i=0; i<c.size(); i++)
      |                 ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:176:1: warning: control reaches end of non-void function [-Wreturn-type]
  176 | }
      | ^
#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...