Submission #295127

#TimeUsernameProblemLanguageResultExecution timeMemory
295127SamAndSplit the Attractions (IOI19_split)C++17
33 / 100
665 ms1048580 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define m_p make_pair #define fi first #define se second #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) typedef long long ll; const int N = 200005; int n, m; vector<int> g[N]; int q[N]; int p0[N]; void dfs0(int x, int p) { p0[x] = p; q[x] = 1; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) continue; dfs0(h, x); q[x] += q[h]; } } pair<int, int> u[4]; vector<int> ans; void dfs(int x, int p, int y) { if (ans[x - 1]) return; if (!u[y].fi) return; ans[x - 1] = u[y].se; --u[y].fi; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i]; if (h == p) continue; dfs(h, x, y); } } vector<int> find_split(int N_, int A, int B, int C, vector<int> P, vector<int> Q) { n = N_; m = sz(P); for (int i = 0; i < m; ++i) { int x = P[i]; int y = Q[i]; ++x; ++y; g[x].push_back(y); g[y].push_back(x); } u[1] = m_p(A, 1); u[2] = m_p(B, 2); u[3] = m_p(C, 3); sort(u + 1, u + 3 + 1); if (u[1].fi == 1) { ans.assign(n, 0); dfs(1, 1, 2); for (int x = 0; x < n; ++x) { if (!ans[x]) { ans[x] = u[1].se; break; } } for (int x = 0; x < n; ++x) { if (!ans[x]) ans[x] = u[3].se; } return ans; } dfs0(1, 1); for (int x = 1; x <= n; ++x) { if (u[1].fi <= min(q[x], n - q[x]) && u[2].fi <= max(q[x], n - q[x])) { ans.assign(n, 0); if (q[x] < n - q[x]) { dfs(x, p0[x], 1); dfs(p0[x], x, 2); } else { dfs(x, p0[x], 2); dfs(p0[x], x, 1); } for (int i = 0; i < n; ++i) { if (!ans[i]) ans[i] = u[3].se; } return ans; } } ans.assign(n, 0); return ans; }

Compilation message (stderr)

split.cpp: In function 'void dfs0(int, int)':
split.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int, int)':
split.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
#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...