제출 #289870

#제출 시각아이디문제언어결과실행 시간메모리
289870IgorISplit the Attractions (IOI19_split)C++17
0 / 100
659 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define forn(i, n) for (int (i) = 0; (i) < (n); (i)++) const int N = 540400; void dfs(int v, int p, vector<vector<int> > &graph, vector<int> &sz, vector<int> &papa) { papa[v] = p; sz[v] = 1; for (auto u : graph[v]) if (u != p) { dfs(u, v, graph, sz, papa); sz[v] += sz[u]; } } vector<int> find_split(int n, int a, int b, int c, vector<int> v, vector<int> u) { vector<pair<int, int> > z = {{a, 1}, {b, 2}, {c, 3}}; sort(all(z)); vector<vector<int> > graph(n); for (int i = 0; i < v.size(); i++) { graph[v[i]].push_back(u[i]); graph[u[i]].push_back(v[i]); } vector<int> sz(n), papa(n); dfs(0, 0, graph, sz, papa); int t = -1, r = 0; for (int i = 0; i < n; i++) { if (sz[i] >= z[0].first && n - sz[i] >= z[1].first) { t = i; r = 0; } if (sz[i] >= z[1].first && n - sz[i] >= z[0].first) { t = i; r = 1; } } if (t == -1) { return vector<int>(n, 0); } vector<int> ans(n); ans[t] = z[r].second; ans[papa[t]] = z[r ^ 1].second; vector<int> q0 = {t}; for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++) { int v = q0[i]; for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++) { int u = graph[v][j]; if (ans[u] == 0) { ans[u] = z[r].second; q0.push_back(u); } } } vector<int> q1 = {papa[t]}; for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++) { int v = q1[i]; for (int j = 1; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++) { int u = graph[v][j]; if (ans[u] == 0) { ans[u] = z[1 ^ r].second; q1.push_back(u); } } } for (int i = 0; i < n; i++) { if (ans[i] == 0) { ans[i] = 3; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
split.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++)
      |                     ~~^~~~~~~~~~~
split.cpp:55:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     for (int i = 0; i < q0.size() && q0.size() < z[r].first; i++)
      |                                      ~~~~~~~~~~^~~~~~~~~~~~
split.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++)
      |                         ~~^~~~~~~~~~~~~~~~~
split.cpp:58:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         for (int j = 0; j < graph[v].size() && q0.size() < z[r].first; j++)
      |                                                ~~~~~~~~~~^~~~~~~~~~~~
split.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++)
      |                     ~~^~~~~~~~~~~
split.cpp:69:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     for (int i = 0; i < q1.size() && q1.size() < z[1 ^ r].first; i++)
      |                                      ~~~~~~~~~~^~~~~~~~~~~~~~~~
split.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 1; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++)
      |                         ~~^~~~~~~~~~~~~~~~~
split.cpp:72:58: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         for (int j = 1; j < graph[v].size() && q1.size() < z[1 ^ r].first; j++)
      |                                                ~~~~~~~~~~^~~~~~~~~~~~~~~~
#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...