제출 #1135288

#제출 시각아이디문제언어결과실행 시간메모리
1135288vibeduckSplit the Attractions (IOI19_split)C++20
7 / 100
35 ms8520 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<vector<int>> vvi; typedef vector<vector<bool>> vvb; typedef vector<vector<ll>> vvll; typedef vector<string> vs; typedef vector<vector<string>> vvs; typedef vector<char> vc; typedef vector<vector<char>> vvc; typedef map<int, int> mii; typedef unordered_map<int, int> umii; const int mxn = 1e5 + 5; vi adj[mxn]; int deg[mxn]; vi ans; int cur = 0; int a1, b1, c1; void dfs(int node, int prev, int i) { ans[node] = i; cur++; //cout << node << " " << i << " " << cur << '\n'; if (i == 1) {if (cur == a1) {i++; cur = 0;}} else if (i == 2) {if (cur == b1) {i++; cur = 0;}} else if (i == 3) {if (cur == c1) {return;}} for (auto neighbour : adj[node]) { if (neighbour == prev) continue; dfs(neighbour, node, i); return; } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { a1 = a; b1 = b; c1 = c; int m = p.size(); ans.resize(n); for (int i = 0; i < m; i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); deg[p[i]]++; deg[q[i]]++; } if (m == n) dfs(0, -1, 1); else { int x = 0; for (int i = 1; i < n; i++) if (deg[i] < deg[x]) x = i; dfs(x, -1, 1); } return ans; }
#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...