Submission #1080119

#TimeUsernameProblemLanguageResultExecution timeMemory
1080119Ghulam_JunaidStations (IOI20_stations)C++17
0 / 100
603 ms940 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1005; int sz[N], pref[N]; vector<int> val, g[N]; void pre_dfs(int v, int p = -1){ sz[v] = 1; for (int u : g[v]){ if (u == p) continue; pre_dfs(u, v); sz[v] += sz[u]; } } void dfs(int v, int p = -1){ pref[v] = 0; for (int u : g[v]){ if (u == p) continue; pref[v] += sz[u]; val[u] = val[v] - sz[v] + pref[v]; dfs(u, v); } } vector<int> label(int n, int k, vector<int> u, vector<int> v){ for (int i = 0; i <= n; i ++) pref[i] = sz[i] = 0, g[i].clear(); val.resize(n, 0); for (int i = 0; i < n - 1; i ++){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } pre_dfs(0); val[0] = sz[0]; dfs(0); set<int> st; for (int x : val) st.insert(x); assert(st.size() == n); return val; } int find_next_station(int s, int t, vector<int> c){ // cout << s << " ?? " << t << endl; for (int x : c){ // cout << "cmp " << x << endl; if (t <= x){ // cout << "goto " << x << endl; return x; } } // cout << "goto " << c.back() << endl; return c.back(); } // int main(){ // int t; // cin >> t; // while (t--){ // int n, k; // cin >> n >> k; // vector<int> u(n - 1), v(n - 1); // for (int i = 0; i < n - 1; i ++) // cin >> u[i] >> v[i]; // label(n, k, u, v); // for (int i = 0; i < n; i ++){ // cout << i << " :: " << val[i] << endl; // } // for (int i = 0; i < n; i ++){ // for (int j = 0; j < n; j ++){ // if (i == j) continue; // vector<int> adj; // for (int x : g[i]) // adj.push_back(val[x]); // sort(adj.begin(), adj.end()); // int res = find_next_station(val[i], val[j], adj); // cout << val[i] << " -- " << val[j] << " == " << res << endl; // } // } // } // } /* 10 10 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 */

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from stations.cpp:1:
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     assert(st.size() == n);
      |            ~~~~~~~~~~^~~~
#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...