Submission #1080102

#TimeUsernameProblemLanguageResultExecution timeMemory
1080102Jawad_Akbar_JJStations (IOI20_stations)C++17
0 / 100
540 ms940 KiB
#include <iostream> #include <vector> using namespace std; const int N1 = 1005; vector<int> nei[N1]; int d[N1]; bool seen[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){ int cur = mn, lb = 0; while (cur != -1){ int ncur = -1; lab[cur] = lb++; seen[cur] = 1; for (int i : nei[cur]) if (!seen[i]) ncur = i; cur = ncur; } return lab; } return lab; } // int ver; // 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, t2 = true; for (int i=0;i<n;i++){ tt &= lab[i] == i+1; if (lab[i] > n) t2 = false; } 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; } } if (t2){ if (s > t) return s - 1; return s + 1; } }

Compilation message (stderr)

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