Submission #1080097

#TimeUsernameProblemLanguageResultExecution timeMemory
1080097Jawad_Akbar_JJStations (IOI20_stations)C++17
8 / 100
642 ms924 KiB
#include <iostream> #include <vector> using namespace std; const int N1 = 1005; vector<int> nei[N1]; int d[N1]; vector<int> label(int n, int k, vector<int> u, vector<int> v){ bool t = 1; for (int i=0;i<n-1;i++){ nei[u[i]].push_back(v[i]); nei[v[i]].push_back(u[i]); d[u[i]]++; d[v[i]]++; t &= min(u[i], v[i]) == i / 2; t &= max(u[i], v[i]) == i+1; } vector<int> lab(n, 0); // if (k == 1e9){ // for (int i=0;i<n-1;i++){ // lab[u[i]] += (1<<v[i]); // lab[v[i]] += (1<<u[i]); // } // lab[0] += 1e8; // return lab; // } if (t){ for (int i=0;i<n;i++) lab[i] = i+1; return lab; } // int mx = 0, mn = 0; // for (int i=0;i<n;i++){ // if (d[i] > d[mx]) // mx = i; // if (d[i] < d[mn]) // mn = i; // } // if (d[mx] <= 2){ // } return lab; } // int ver; bool seen[10000]; // bool dfs(int u, int s, int t, int p = -1){ // if (u == t) // return 1; // seen[u] = 1; // for (int i : nei[u]){ // if (seen[i]) // continue; // bool b = dfs(i, s, t, u); // if (b and u == s) // ver = i; // if (b) // return 1; // } // return 0; // } int find_next_station(int s, int t, vector<int> lab){ int n = lab.size(); for (int i=0;i<n;i++) nei[i].clear(), seen[i] = 0; // if (lab[0] > 1e8){ // lab[0] -= 1e8; // for (int i=0;i<n;i++){ // for (int j=0;j<n;j++) // if ((1<<j) & lab[i]) // nei[i].push_back(j); // } // lab[0] += 1e8; // ver = -1; // bool b = dfs(s, s, t); // if (ver == -1) // return lab[0]; // return lab[ver]; // } bool tt = true; for (int i=0;i<n;i++) tt &= lab[i] == i+1; if (tt and lab[0] == 1){ if (s < t){ for (int i=1;i<=30;i++) if ((t>>i) == s) return (t >> (i-1)); return s / 2; } else{ return s / 2; } } }

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^
#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...