제출 #152135

#제출 시각아이디문제언어결과실행 시간메모리
152135arnold518Cats or Dogs (JOI18_catdog)C++14
100 / 100
1006 ms26356 KiB
#include "catdog.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const int INF = 1e6; int N; vector<int> adj[MAXN+10]; int sz[MAXN+10], par[MAXN+10], dep[MAXN+10]; int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10]; int A[MAXN+10], C[MAXN+10], D[MAXN+10]; struct Node { int AA, AB, BA, BB; Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {} Node() : AA(0), AB(0), BA(0), BB(0) {} }; Node combine(Node lc, Node rc) { Node ret; ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA}); ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB}); ret.BA=min({lc.BA+rc.AA, lc.BA+rc.BA+1, lc.BB+rc.AA+1, lc.BB+rc.BA}); ret.BB=min({lc.BA+rc.AB, lc.BA+rc.BB+1, lc.BB+rc.AB+1, lc.BB+rc.BB}); return ret; } struct SEG { Node tree[MAXN*4+10]; void init(int node, int tl, int tr) { if(tl==tr) { tree[node]=Node(0, INF, INF, 0); return; } int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); tree[node]=combine(tree[node*2], tree[node*2+1]); } void update(int node, int tl, int tr, int pos, Node val) { if(tr<pos || pos<tl) return; if(tl==tr) { tree[node]=val; return; } int mid=tl+tr>>1; update(node*2, tl, mid, pos, val); update(node*2+1, mid+1, tr, pos, val); tree[node]=combine(tree[node*2], tree[node*2+1]); } void query(int node, int tl, int tr, int l, int r, vector<Node> &ret) { if(l<=tl && tr<=r) { ret.push_back(tree[node]); return; } if(r<tl || tr<l) return; int mid=tl+tr>>1; query(node*2, tl, mid, l, r, ret); query(node*2+1, mid+1, tr, l, r, ret); } Node query(int l, int r) { int i, j; vector<Node> V; query(1, 1, N, l, r, V); Node ret=V[0]; for(i=1; i<V.size(); i++) ret=combine(ret, V[i]); return ret; } void debug(int node, int tl, int tr) { printf("%d %d %d : %d %d %d %d\n", node, tl, tr, tree[node].AA, tree[node].AB, tree[node].BA, tree[node].BB); if(tl==tr) return; int mid=tl+tr>>1; debug(node*2, tl, mid); debug(node*2+1, mid+1, tr); } }seg; void dfs(int now, int bef, int depth) { sz[now]=1; par[now]=bef; dep[now]=depth; for(int nxt : adj[now]) { if(nxt==bef) continue; dfs(nxt, now, depth+1); sz[now]+=sz[nxt]; } } void hld(int now, int bef) { idx[now]=cnt++; int heavy=0; for(int nxt : adj[now]) { if(nxt==bef) continue; if(sz[heavy]<sz[nxt]) heavy=nxt; } if(heavy==0) { tail[now]=now; return; } head[heavy]=head[now]; hld(heavy, now); for(int nxt : adj[now]) { if(nxt==bef || nxt==heavy) continue; head[nxt]=nxt; hld(nxt, now); } tail[now]=tail[heavy]; } void initialize(int _N, vector<int> A, vector<int> B) { int i, j; N=_N; for(i=0; i<N-1; i++) { adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } dfs(1, 0, 1); head[1]=1; hld(1, 0); seg.init(1, 1, N); } int query(int u, int val) { Node chg; if(val==0) chg=Node(C[u], INF, INF, D[u]); if(val==1) { Node t=seg.query(idx[u], idx[u]); D[u]=t.BB; chg=Node(C[u], INF, INF, INF); } if(val==2) { Node t=seg.query(idx[u], idx[u]); C[u]=t.AA; chg=Node(INF, INF, INF, D[u]); } A[u]=val; while(head[u]!=1) { int a=par[head[u]], b=head[u]; Node qa=seg.query(idx[a], idx[a]), qb=seg.query(idx[head[b]], idx[tail[b]]); if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); seg.update(1, 1, N, idx[u], chg); qb=seg.query(idx[head[b]], idx[tail[b]]); if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); chg=qa; u=par[head[u]]; } seg.update(1, 1, N, idx[u], chg); Node ans=seg.query(idx[head[1]], idx[tail[1]]); //seg.debug(1, 1, N); printf("===========================\n"); return min({ans.AA, ans.AB, ans.BA, ans.BB}); } int cat(int u) { return query(u, 1); } int dog(int u) { return query(u, 2); } int neighbor(int u) { return query(u, 0); }

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

catdog.cpp: In member function 'void SEG::init(int, int, int)':
catdog.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::update(int, int, int, int, Node)':
catdog.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'void SEG::query(int, int, int, int, int, std::vector<Node>&)':
catdog.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int)':
catdog.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
                  ~^~~~~~~~~
catdog.cpp:74:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
catdog.cpp: In member function 'void SEG::debug(int, int, int)':
catdog.cpp:86:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
catdog.cpp: In function 'int query(int, int)':
catdog.cpp:174:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
         ^~
catdog.cpp:174:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
                                                                         ^
catdog.cpp:175:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
         ^~
catdog.cpp:175:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
                                                                         ^
catdog.cpp:178:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
         ^~
catdog.cpp:178:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1); C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
                                                                         ^
catdog.cpp:179:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
         ^~
catdog.cpp:179:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)); D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
                                                                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...