제출 #94799

#제출 시각아이디문제언어결과실행 시간메모리
94799shoemakerjoCats or Dogs (JOI18_catdog)C++14
100 / 100
598 ms22848 KiB
#include "catdog.h" #include <bits/stdc++.h> using namespace std; int n; const int maxn = 100010; const int inf = 1000000000; int subsize[maxn]; int bigch[maxn]; int myspot[maxn]; int mycol[maxn]; //store the current color of this node vector<int> preorder; //this is the special preorder thing vector<int> adj[maxn]; int par[maxn]; int chainhead[maxn]; //pretty sure this is all that matters //don't need tail?? int chainend[maxn]; int ccost[maxn][2]; //cost of being colored 1 or 2 int pardiff[maxn][2]; struct mat { int v[2][2]; }; const bool debug = false; mat seg[maxn*4]; void printmat(mat & thing) { cout << thing.v[0][0] << ", " << thing.v[0][1] << ", " << thing.v[1][0] << ", " << thing.v[1][1] << endl; } mat merge(mat& a, mat& b) { //no reason to not pass by reference mat res; res.v[0][0] = res.v[0][1] = res.v[1][0] = res.v[1][1] = inf; for (int i = 0; i <= 1; i++) { for (int j = 0; j <= 1; j++) { res.v[i][j] = min(res.v[i][j], a.v[i][0] + b.v[0][j]); res.v[i][j] = min(res.v[i][j], a.v[i][0] + 1 + b.v[1][j]); res.v[i][j] = min(res.v[i][j], a.v[i][1] + 1 + b.v[0][j]); res.v[i][j] = min(res.v[i][j], a.v[i][1] + b.v[1][j]); } } // if (debug) { // cout << " merge of "; // printmat(a); // cout << " and "; // printmat(b); // cout << " produces "; // printmat(res); // } return res; } void predfs(int u, int p = -1) { par[u] = p; if (debug) cout << u << " has parent " << p << endl; subsize[u] = 1; for (int v : adj[u]) { if (v == p) continue; predfs(v, u); subsize[u] += subsize[v]; if (subsize[v] > subsize[bigch[u]]) { bigch[u] = v; } } } void dfs(int u) { preorder.push_back(u); myspot[u] = preorder.size()-1; if (par[u] != -1 && bigch[par[u]] == u) { chainhead[u] = chainhead[par[u]]; } else chainhead[u] = u; if (debug) cout << "dfs: " << u << " has head " << chainhead[u] << endl; chainend[chainhead[u]] = u; //now I am the smallest if (bigch[u]) { dfs(bigch[u]); } for (int v : adj[u]) { if (v != bigch[u] && v != par[u]) { dfs(v); } } } void buildtree(int ss = 1, int se = n, int si = 0) { //pretty sure this is a useless method if (ss == se) { seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf; if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1]; if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0]; return; } int mid = (ss+se)/2; buildtree(ss, mid, si*2+1); buildtree(mid+1, se, si*2+2); seg[si] = merge(seg[si*2+1], seg[si*2+2]); } void upd(int spot, int ss = 1, int se = n, int si = 0) { if (ss == se) { //update explicitly seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf; if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1]; if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0]; if (debug) { cout << "updating " << spot << endl; cout << " "; printmat(seg[si]); } return; } int mid = (ss+se)/2; if (spot <= mid) upd(spot, ss, mid, si*2+1); else upd(spot, mid+1, se, si*2+2); seg[si] = merge(seg[si*2+1], seg[si*2+2]); } mat zs; //zeroes mat query(int qs, int qe, int ss = 1, int se = n, int si = 0) { if (qs > qe || ss > se || qs > se || qe < ss) return zs; if (qs <= ss && se <= qe) { return seg[si]; } int mid = (ss+se)/2; if (qs > mid) { return query(qs, qe, mid+1, se, si*2+2); } if (qe <= mid) { return query(qs, qe, ss, mid, si*2+1); } mat lhs = query(qs, qe, ss, mid, si*2+1); mat rhs = query(qs, qe, mid+1, se, si*2+2); return merge(lhs, rhs); } int uph(int u) { //update up the HLD structure // if (debug) cout << "start of an HLD trek: "; while (true) { //should return eventually int nx = chainhead[u]; // cout << u << " goes to " << nx << endl; upd(myspot[u]); if (debug) { cout << " " << u << " :: " << ccost[u][0] << " - " << ccost[u][1] << endl; mat cccc = query(myspot[u], myspot[u]); cout << " "; printmat(cccc) ; } mat cv = query(myspot[nx], myspot[chainend[nx]]); int c0 = min(cv.v[0][0], cv.v[0][1]); int c1 = min(cv.v[1][0], cv.v[1][1]); // if (debug) cout << u << " "; if (nx == 1) { // cout << "THING THING: "; // printmat(cv); // if (debug) cout << 1 << endl; if (debug) cout << c0 << " VVVVV " << c1 << endl; // if (debug) cout << "CCOSTS: " << ccost[1][0] << " -- " << ccost[1][1] << endl; return min(c0, c1); } // if (debug) cout << " at " << u << " with " << c0 << " and " << c1 << endl; // if (debug) { // cout << " "; // printmat(cv); // } int op = par[nx]; ccost[op][0] += min(c0, c1 + 1) - min(pardiff[nx][0], pardiff[nx][1] + 1); ccost[op][1] += min(c1, c0 + 1) - min(pardiff[nx][1], pardiff[nx][0] + 1); pardiff[nx][0] = c0; pardiff[nx][1] = c1; u = op; } } void initialize(int N, vector<int> A, vector<int> B) { n = N; for (int i = 0; i < N-1; i++) { adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } par[1] = -1; preorder.push_back(-1); //just buffer it so I can one-index predfs(1); dfs(1); //this is to get the preorder buildtree(); //do not need this because the answer is zs.v[0][1] = zs.v[1][0] = inf; // cout << "DONE WITH INIT" << endl; } int cat(int v) { if (debug) cout << "CAT at " << v << endl; mycol[v] = 1; return uph(v); } int dog(int v) { if (debug) cout << "DOG at " << v << endl; mycol[v] = 2; if (debug) uph(v); if (debug) { for (int i = 1; i <= n; i++) { cout << i << " ::: "; mat cc = query(myspot[i], myspot[i]); printmat(cc); } } return uph(v); } int neighbor(int v) { if (debug) cout << "EMPTY at " << v << endl; mycol[v] = 0; return uph(v); } //THIS IS DONE IN THE WEIRD IOI STYLE //MUST BE DONE ONLINE //let's do the HLD thing where ranges are consecutive in a single segment tree
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...