제출 #784322

#제출 시각아이디문제언어결과실행 시간메모리
784322Magikarp4000Split the Attractions (IOI19_split)C++17
18 / 100
81 ms26468 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; const int MAXN = 1e5+5; int n,m,a,b,c; vector<int> v[MAXN], v1[MAXN], res, cur; int p[MAXN], sz[MAXN], cnt; bool z[MAXN], bad[MAXN]; void dfs(int s, int pa) { z[s] = sz[s] = 1; FORX(u,v[s]) { if (z[u]) continue; dfs(u,s); p[u] = s; sz[s] += sz[u]; v1[s].PB(u); v1[u].PB(s); } } void dfs1(int s, int pa, int ub, int idx) { if (cnt < ub) { res[s] = idx; cnt++; } FORX(u,v1[s]) if (u != pa) dfs1(u,s,ub,idx); } void dfs2(int s, int pa, int ub) { if (cnt < ub) { cur.PB(s); cnt++; } FORX(u,v1[s]) if (u != pa) dfs2(u,s,ub); } bool check(int s, int pa, PII h[3]) { cnt = 0; cur.clear(); dfs2(s,pa,h[1].F); if (cnt == h[1].F) { FORX(u,cur) res[u] = h[1].S; FOR(i,0,n) if (!res[i]) res[i] = h[2].S; return 1; } return 0; } vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) { n = N, a = A, b = B, c = C, m = P.size(); res.resize(n,0); cur.resize(n,0); PII h[3] = {{a,1}, {b,2}, {c,3}}; sort(h,h+3); vector<int> noob(n,0); FOR(i,0,m) { v[P[i]].PB(Q[i]); v[Q[i]].PB(P[i]); } p[0] = -1; dfs(0,-1); // FOR(i,1,n) { // if (p[i] == -1) { // while (true) int bruh = 0; // } // } int mi = INF, x = -1; FOR(i,0,n) { if (sz[i] >= h[0].F && sz[i] < mi) { mi = sz[i]; x = i; } } // if (x == -1 || x == 0) return noob; dfs1(x,p[x],h[0].F,h[0].S); if (p[x] != -1) { check(p[x],x,h); return res; } // if (p[x] != -1 && check(p[x],x,h)) return res; // FOR(i,0,n) { // if (!res[i]) continue; // FORX(u,v[i]) { // if (u == p[i]) continue; // if (check(u,i,h)) return res; // } // } return noob; }

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

split.cpp: In function 'void dfs(int, int)':
split.cpp:33:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |     z[s] = sz[s] = 1;
      |            ~~~~~~^~~
#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...