Submission #955696

#TimeUsernameProblemLanguageResultExecution timeMemory
955696MackerSplit the Attractions (IOI19_split)C++17
40 / 100
67 ms22728 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define ff first #define ss second #define all(v) v.begin(), v.end() #define FOR(i, n) for (int i = 0; i < n; i++) vector<vector<int>> adj; vector<vector<int>> chld; vector<bool> vis; vector<int> res; vector<pii> f; vector<int> coln; int v = -1; bool r = 0; int n; int dfs(int a){ vis[a] = 1; int ret = 1; for (auto b : adj[a]) { if(!vis[b]){ ret += dfs(b); chld[a].push_back(b); } } if(v != -1) return ret; if((ret >= f[0].ff && n - ret >= f[1].ff) || (ret >= f[1].ff && n - ret >= f[0].ff)) v = a; if((ret >= f[1].ff && n - ret >= f[0].ff)) r = 1; return ret; } void coldfs(int a, int col){ if(coln[col-1] == 0) return; res[a] = col; coln[col-1]--; for (auto b : chld[a]) { if(!res[b]){ coldfs(b, col); } } } vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) { n = nn; f = {{a, 1}, {b, 2}, {c, 3}}; coln = {a, b, c}; adj.assign(n, {}); chld.assign(n, {}); vis.assign(n, 0); res.assign(n, 0); FOR(i, p.size()){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } sort(all(f)); dfs(0); if(v == -1) return res; if(r) { coldfs(v, f[1].ss); coldfs(0, f[0].ss); } else{ coldfs(v, f[0].ss); coldfs(0, f[1].ss); } FOR(i, n) if(res[i] == 0) res[i] = f[2].ss; return res; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:12:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, n) for (int i = 0; i < n; i++)
......
   58 |  FOR(i, p.size()){
      |      ~~~~~~~~~~~                     
split.cpp:58:2: note: in expansion of macro 'FOR'
   58 |  FOR(i, p.size()){
      |  ^~~
#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...