이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9 + 7;
const int BASE = 137;
const int szBL = 350;
int n, m, A, B, C;
vector<int> ke[N];
namespace sub1 {
bool check () {
if (m > n) return 0;
rep (u, 1, n) if (SZ(ke[u]) > 2) return 0;
return 1;
}
vector<int> solution () {
vector<int> Ans(n + 2, 0), dd(n + 2, 0);
function<void(int, int)> dfs = [&] (int u, int p) {
static int time_dfs = 0;
++time_dfs;
if (time_dfs <= A) Ans[u] = 1;
else if (time_dfs <= A + B) Ans[u] = 2;
else Ans[u] = 3;
dd[u] = 1;
iter (&v, ke[u]) {
if (v == p || dd[v]) continue;
dfs(v, u);
}
};
dfs(1, 0);
// rep (i, 1, n) cout << Ans[i] <<" ";
vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
return subAns;
}
}
namespace sub2 {
bool check () {
return A == 1;
}
vector<int> solution() {
vector<vector<int>> adj(n + 3);
vector<int> deg(n + 3, 0), dd(n + 3, 0);
function<void(int)> dfs = [&] (int u) {
dd[u] = 1;
iter (&v, ke[u]) {
if (dd[v]) continue;
adj[u].pb(v);
adj[v].pb(u);
dfs(v);
}
};
dfs(1);
queue<int> Q;
rep (u, 1, n) {
deg[u] = SZ(adj[u]);
if (deg[u] == 1) {
Q.push(u);
}
}
vector<int> Ans(n + 3, 2);
int step = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
++step;
if (step <= A) Ans[u] = 1;
else if (step <= A + C) Ans[u] = 3;
deg[u] = -1;
iter (&v, adj[u]) {
--deg[v];
if (deg[v] == 1) Q.push(v);
}
}
// rep (i, 1, n) cout << Ans[i] <<" ";
vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
return subAns;
}
}
namespace sub3 {
bool check () {
return m == n - 1;
}
vector<int> solution () {
int idA, idB, idC; { ///màu gốc của màu A
vector<pii> vec = { MP(A, 1), MP(B, 2), MP(C, 3) };
sort (ALL(vec));
tie(A, idA) = vec[0], tie(B, idB) = vec[1], tie(C, idC) = vec[2];
}
int st = -1, ed = -1;///st < ed
vector<int> szC(n + 3, 0);
function<void(int, int)> dfs = [&] (int u, int p) {
szC[u] = 1;
iter (&v, ke[u]) {
if (v == p) continue;
dfs(v, u);
pii c1 = {u, n - szC[v]}, c2 = {v, szC[v]};
if (c1.se > c2.se) swap(c1, c2);
if (c1.se >= A && c2.se >= B) {
st = c1.fs;
ed = c2.fs;
}
szC[u] += szC[v];
}
};
dfs(1, 0);
if (st == -1) {
// rep (i, 1, n) cout << 0 <<" ";
return vector<int> (n, 0);
}
vector<int> Ans(n + 3, idC);
vector<int> szCol(4, 0);
szCol[idA] = A;
szCol[idB] = B;
function<void(int, int, int)> color = [&] (int u, int p, int col){
if (szCol[col] > 0)
Ans[u] = col;
--szCol[col];
iter (&v, ke[u]) {
if (v != p) color (v, u, col);
}
};
color (st, ed, idA);
color (ed, st, idB);
// rep (i, 1, n) cout << Ans[i] <<" ";
vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
return subAns;
}
}
namespace sub4 {
struct Disjoint_set {
int lab[N], sz[N];
void init (int n) {
rep (i, 1, n) lab[i] = i, sz[i] = 1;
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
void Join (int u, int v) {
u = Find(u);
v = Find(v);
if (v == u) return;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
lab[v] = u;
}
}DSU;
vector<int> solution() {
int idA, idB, idC; { ///màu gốc của màu A
vector<pii> vec = { MP(A, 1), MP(B, 2), MP(C, 3) };
sort (ALL(vec));
tie(A, idA) = vec[0], tie(B, idB) = vec[1], tie(C, idC) = vec[2];
}
vector<int> candidates; {
rep (i, 1, n) candidates.pb(i);
random_shuffle(ALL(candidates));
candidates.resize(min(n, 100));
}
vector<int> Ans;
bool ok = 0;
auto process = [&] (int curR) {
vector<vector<int>> adj(n + 3);
vector<int> deg(n + 3, 0), dd(n + 3, 0);
function<void(int)> dfs = [&] (int u) -> pair<bool, vector<int>> {
dd[u] = 1;
random_shuffle(ALL(ke[u]));
iter (&v, ke[u]) {
if (dd[v]) continue;
adj[u].pb(v);
adj[v].pb(u);
dfs(v);
}
};
dfs(curR);
queue<int> Q;
rep (u, 1, n) {
deg[u] = SZ(adj[u]);
if (deg[u] == 1) {
Q.push(u);
}
}
int numA = n;
int rootB = -1;
vector<int> res(n + 3, idA);
DSU.init(n);
while (numA > A) {
int u = Q.front();
Q.pop();
--numA;
res[u] = idC;
// cout << u <<"\n";
deg[u] = -1;
iter (&v, adj[u]) {
if (deg[v] != -1) {
--deg[v];
if (deg[v] == 1) Q.push(v);
}
}
iter (&v, ke[u]) {
if (deg[v] == -1) {
DSU.Join(u, v);
}
}
int curRoot = DSU.Find(u);
if (DSU.sz[curRoot] >= B) {
rootB = curRoot;
}
}
if (rootB == -1) return MP(0, vector<int> ());
int szB = B;
dd.assign(n + 3, 0);
function<void(int)> coloring = [&] (int u) {
if (szB > 0) res[u] = idB;
--szB;
dd[u] = 1;
iter (&v, ke[u]) {
if (deg[v] != -1 || dd[v]) continue;
coloring(v);
}
};
coloring(rootB);
return MP(1, res);
};
rep (step, 0, SZ(candidates) - 1) {
tie(ok, Ans) = process(candidates[step]);
if (ok) break;
}
// rep (i, 1, n) cout << Ans[i] <<" ";
if (!ok)
return vector<int> (n, 0);
vector<int> subAns (Ans.begin() + 1, Ans.begin() + 1 + n);
return subAns;
}
}
vector<int> find_split (int _n, int _A, int _B, int _C, vector<int> _u, vector<int> _v) {
n = _n;
m = SZ(_u);
A = _A;
B = _B;
C = _C;
rep (i, 1, m) {
int u = _u[i - 1], v = _v[i - 1];
++u, ++v;
ke[u].pb(v);
ke[v].pb(u);
}
// if (sub1 :: check()) return sub1 :: solution();
// else if (sub2 :: check()) return sub2 :: solution();
// else if (sub3 :: check()) return sub3 :: solution();
// else
return sub4 :: solution();
}
void solution () {
vector<int> cur = find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5}, {1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
iter (&id, cur) cout << id <<" ";
cout<<"\n";
// cin >> n >> m >> A >> B >> C;
// rep (i, 1, m) {
// int u, v;
// cin >> u >> v;
// ke[u].pb(v);
// ke[v].pb(u);
// }
// if (sub1 :: check()) sub1 :: solution();
// else if (sub2 :: check()) sub2 :: solution();
// else sub3 :: solution();
}
//#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
//main () {
//// file("DIAMETER");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
no bug challenge +21
1 2
2 8
8 4
1 9
1 3
1 7
7 6
6 5
cận trên để giảm không gian và thời gian của mô hình bài toán
cận dưới để có thêm insight về kết quả bài toán
gọi sao cho có lợi cho mình nhất
*/
컴파일 시 표준 에러 (stderr) 메시지
split.cpp: In lambda function:
split.cpp:198:13: warning: no return statement in function returning non-void [-Wreturn-type]
198 | };
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |