Submission #565957

#TimeUsernameProblemLanguageResultExecution timeMemory
565957InternetPerson10Stray Cat (JOI20_stray)C++17
0 / 100
45 ms15772 KiB
#include "Anthony.h" #include <bits/stdc++.h> using namespace std; #include <vector> namespace { // orig: 1 1 0 1 0 0 vector<int> sixchain = {1, 0, 1, 1, 1, 0}; vector<vector<pair<int, int>>> adj; vector<int> marks, chain; struct dsu { vector<int> par, siz; dsu(int n) { par.resize(n); siz.resize(n, 1); for(int i = 0; i < n; i++) par[i] = i; } int get(int x) { if(par[x] == x) return x; return par[x] = get(par[x]); } bool unite(int x, int y) { x = get(x); y = get(y); if(x == y) return false; if(siz[x] > siz[y]) swap(x, y); par[x] = y; siz[y] += siz[x]; return true; } }; void dfs(int n, int par = -1, int na = -1, int ne = -1) { if(na != -1) { if(adj[par].size() == 2) { chain[n] = (chain[par] + 1) % 6; if(ne == -1) marks[na] = 0; else marks[na] = (sixchain[chain[n]] + marks[ne]) % 2; } else { chain[n] = -1; if(ne == -1) marks[na] = 0; else marks[na] = (1 + marks[ne]) % 2; } } for(auto p : adj[n]) { int ch, nu; tie(ch, nu) = p; if(ch == par) continue; dfs(ch, n, nu, na); } } } // namespace vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) { marks.resize(M, 0); chain.resize(N, 0); adj.resize(N); if(M != N - 1) { dsu uf(N); vector<int> v1, v2; for(int i = 0; i < M; i++) { if(!uf.unite(U[i], V[i])) { U[i] = V[i] = -1; marks[i] = 2; } } } for(int i = 0; i < M; i++) { if(U[i] == -1) continue; adj[U[i]].push_back({V[i], i}); adj[V[i]].push_back({U[i], i}); } dfs(0); return marks; }
#include "Catherine.h" #include <bits/stdc++.h> using namespace std; namespace { vector<int> sixchain = {1, 1, 0, 1, 0, 0}; vector<vector<pair<int, int>>> adj; vector<int> marks, chain; struct dsu { vector<int> par, siz; dsu(int n) { par.resize(n); siz.resize(n, 1); for(int i = 0; i < n; i++) par[i] = i; } int get(int x) { if(par[x] == x) return x; return par[x] = get(par[x]); } bool unite(int x, int y) { x = get(x); y = get(y); if(x == y) return false; if(siz[x] > siz[y]) swap(x, y); par[x] = y; siz[y] += siz[x]; return true; } }; void dfs(int n, int par = -1, int na = -1) { if(na != -1) { if(adj[par].size() == 2) { chain[n] = (chain[par] + 1) % 6; marks[na] = (sixchain[chain[n]] + chain[par]) % 2; } else { chain[n] = -1; marks[na] = (1 + chain[par]) % 2; } } for(auto p : adj[n]) { int ch, nu; tie(ch, nu) = p; if(ch == par) continue; dfs(ch, n, nu); } } vector<int> marksGot; int goBack = -1; int goUp = 0; set<vector<int>> goingDown = { {1, 1, 0, 1, 0, 0}, {1, 0, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 1}, {1, 0, 0, 1, 1, 0}, {0, 0, 1, 1, 0, 1}, {0, 1, 1, 0, 1, 0} }; } // namespace void Init(int A, int B) { } vector<int> y; int findVal(int x) { marksGot.push_back(x); return x; } int Move(std::vector<int> k) { y = k; int ySize = y[0] + y[1], mini = 2; if(y[0]) mini = 0; else mini = 1; if(marksGot.size() == 0) { if(ySize == 1) { goUp = 1; return findVal(mini); } if(ySize == 2) { return findVal(mini); } goUp = 1; if(y[0] == 1) return findVal(0); return findVal(1); } if(goBack > -1) { goBack--; if(goBack == -1) goUp = 1; return findVal(marksGot[goBack+1]); } if(goUp) { if(ySize == 1) { return findVal(mini); } int x = marksGot.back(); return findVal(1-x); } if(ySize == 0) { // Reached leaf marksGot.push_back(marksGot.back()); goUp = 1; return -1; } if(ySize == 1 && marksGot.size() < 6) { return findVal(mini); } if(ySize == 1 && marksGot.size() == 6) { if(goingDown.count(marksGot)) { goBack = 4; marksGot.push_back(marksGot[5]); return -1; } else { // Going up na pala goUp = 1; return findVal(mini); } } if(ySize > 1) { goUp = 1; if(y[0] == 0) { marksGot.push_back(1); return -1; } if(y[1] == 0) { marksGot.push_back(0); return -1; } return findVal(1-marksGot.back()); } while(true) {} assert(false); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...