제출 #239156

#제출 시각아이디문제언어결과실행 시간메모리
239156karmaCats or Dogs (JOI18_catdog)C++14
100 / 100
1319 ms28408 KiB
#include <bits/stdc++.h> #include "catdog.h" #define pb emplace_back #define ll long long #define fi first #define se second #define mp make_pair //#define int int64_t using namespace std; const int N = (int)1e5 + 2; const int inf = 2e5; int n, u, v, q, sz[N], cur[N], par[N], t, tail[N]; int cnt, cntp, head[N], pos[N], id[N], big[N]; vector<int> adj[N]; int l[N << 2], h[N << 2]; struct TNode { int g[2][2]; TNode() {g[0][0] = g[1][1] = 0, g[1][0] = g[0][1] = inf;} TNode operator +(const TNode& r)const& { TNode res; res.g[0][0] = min({g[0][1] + r.g[1][0], g[0][1] + r.g[0][0] + 1, g[0][0] + r.g[0][0], g[0][0] + r.g[1][0] + 1, inf}); res.g[0][1] = min({g[0][1] + r.g[1][1], g[0][1] + r.g[0][1] + 1, g[0][0] + r.g[0][1], g[0][0] + r.g[1][1] + 1, inf}); res.g[1][0] = min({g[1][1] + r.g[1][0], g[1][1] + r.g[0][0] + 1, g[1][0] + r.g[0][0], g[1][0] + r.g[1][0] + 1, inf}); res.g[1][1] = min({g[1][1] + r.g[1][1], g[1][1] + r.g[0][1] + 1, g[1][0] + r.g[0][1], g[1][0] + r.g[1][1] + 1, inf}); return res; } } st[N << 2], val; void build(int x, int low, int high) { l[x] = low, h[x] = high; if(low == high) return; int mid = (low + high) >> 1; build(x << 1, low, mid); build(x << 1 | 1, mid + 1, high); } void upd(int x, int pos, int add0, int add1) { if(l[x] > pos || h[x] < pos) return; if(l[x] == pos && h[x] == pos) { st[x].g[0][0] += add0; st[x].g[1][1] += add1; return; } upd(x << 1, pos, add0, add1); upd(x << 1 | 1, pos, add0, add1); st[x] = st[x << 1] + st[x << 1 | 1]; } TNode get(int x, int low, int high) { if(low > high) return TNode(); if(low > h[x] || l[x] > high) return TNode(); if(low <= l[x] && h[x] <= high) return st[x]; return get(x << 1, low, high) + get(x << 1 | 1, low, high); } void hld(int u) { if(!head[cnt]) head[cnt] = u; id[u] = cnt, pos[u] = ++cntp, tail[cnt] = u; for(int v: adj[u]) if(!big[u] || sz[v] > sz[big[u]]) big[u] = v; if(big[u]) hld(big[u]); for(int v: adj[u]) if(big[u] != v) ++cnt, hld(v); } void initialize(int N, vector<int> A, vector<int> B) { n = N; for(int i = 0; i < A.size(); ++i) { adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]); } function<void(int)> dfs = [&](int u) { sz[u] = 1; for(int& v: adj[u]) { if(v == par[u]) swap(v, adj[u].back()); if(v == par[u]) continue; par[v] = u; dfs(v); sz[u] += sz[v]; } if(par[u]) adj[u].pop_back(); }; dfs(1), cnt = 1, hld(1); build(1, 1, n); fill(cur, cur + n + 1, -1); } int f0, f1, top, nf0, nf1; pair<int, int> getf(int l, int r) { val = get(1, pos[l], pos[r]); return mp(min({val.g[0][0], val.g[0][1], val.g[1][0] + 1, val.g[1][1] + 1}), min({val.g[1][0], val.g[1][1], val.g[0][0] + 1, val.g[0][1] + 1})); } void update(int v, int add0, int add1) { while(1) { top = head[id[v]]; tie(f0, f1) = getf(top, tail[id[v]]); upd(1, pos[v], add0, add1); tie(nf0, nf1) = getf(top, tail[id[v]]); if(top == 1) return; add0 = nf0 - f0, add1 = nf1 - f1, v = par[top]; } } int getans() { tie(f0, f1) = getf(1, tail[1]); return min(f0, f1); } int cat(int v) { cur[v] = 0; update(v, 0, inf); return getans(); } int dog(int v) { cur[v] = 1; update(v, inf, 0); return getans(); } int neighbor(int v) { if(cur[v] == 1) update(v, -inf, 0); else if(cur[v] == 0) update(v, 0, -inf); cur[v] = -1; return getans(); }

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

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); ++i) {
                    ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...