Submission #131764

#TimeUsernameProblemLanguageResultExecution timeMemory
131764dualityCats or Dogs (JOI18_catdog)C++11
100 / 100
816 ms24204 KiB
#define DEBUG 1 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #include "catdog.h" int n; vi adjList[100000]; int parent[100000],size[100000],depth[100000],heavy[100000]; int chain[100000],disc[100000],head[100000],tail[100000],csize[100000]; int c = 0,num = 0; int curr[100000],dp[100000][2]; struct node { int cc,cd,dc,dd; }; node com(node a,node b) { if (a.cc == -1) return b; else if (b.cc == -1) return a; node c; c.cc = min(min(min(a.cc+b.cc,a.cd+b.dc),min(a.cd+b.cc,a.cc+b.dc)+1),(int) 1e9); c.cd = min(min(min(a.cc+b.cd,a.cd+b.dd),min(a.cd+b.cd,a.cc+b.dd)+1),(int) 1e9); c.dc = min(min(min(a.dc+b.cc,a.dd+b.dc),min(a.dd+b.cc,a.dc+b.dc)+1),(int) 1e9); c.dd = min(min(min(a.dc+b.cd,a.dd+b.dd),min(a.dd+b.cd,a.dc+b.dd)+1),(int) 1e9); return c; } node tree[1 << 18]; int build(int s,int e,int i) { if (s == e) { tree[i] = (node){0,(int) 1e9,(int) 1e9,0}; return 0; } int mid = (s+e) / 2; build(s,mid,2*i+1),build(mid+1,e,2*i+2); tree[i] = com(tree[2*i+1],tree[2*i+2]); return 0; } int update(int s,int e,int ai,int i,int c,int d) { if ((s > ai) || (e < ai)) return 0; else if (s == e) { tree[i].cc += c,tree[i].dd += d; return 0; } int mid = (s+e) / 2; update(s,mid,ai,2*i+1,c,d),update(mid+1,e,ai,2*i+2,c,d); tree[i] = com(tree[2*i+1],tree[2*i+2]); return 0; } node query(int s,int e,int qs,int qe,int i) { if ((s > qe) || (e < qs)) return (node){-1,-1,-1,-1}; else if ((s >= qs) && (e <= qe)) return tree[i]; int mid = (s+e) / 2; return com(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2)); } pii query(int u) { node r = query(0,n-1,disc[head[chain[u]]],disc[tail[chain[u]]],0); int c = min(r.cc,r.cd),d = min(r.dc,r.dd); return mp(min(c,d+1),min(d,c+1)); } int doDFS(int u,int p,int d) { int i; parent[u] = p,depth[u] = d,size[u] = 1,heavy[u] = -1; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { size[u] += doDFS(v,u,d+1); if ((heavy[u] == -1) || (size[v] > size[heavy[u]])) heavy[u] = v; } } return size[u]; } int doHLD(int u,int p) { int i; chain[u] = c,disc[u] = num++; if (csize[c] == 0) head[c] = u; csize[c]++,tail[c] = u; if (heavy[u] != -1) doHLD(heavy[u],u); for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if ((v != p) && (v != heavy[u])) c++,doHLD(v,u); } return 0; } void initialize(int N,vector<int> A,vector<int> B) { int i; n = N; for (i = 0; i < N-1; i++) { A[i]--,B[i]--; adjList[A[i]].pb(B[i]); adjList[B[i]].pb(A[i]); } doDFS(0,-1,0),doHLD(0,-1),build(0,N-1,0); } int update(int u,int c,int d) { while (u != -1) { pii a = query(u); update(0,n-1,disc[u],0,c,d); pii b = query(u); c = b.first-a.first,d = b.second-a.second; u = parent[head[chain[u]]]; } return 0; } int cat(int v) { v--,curr[v] = 1,update(v,0,1e9); pii ans = query(0); return min(ans.first,ans.second); } int dog(int v) { v--,curr[v] = 2,update(v,1e9,0); pii ans = query(0); return min(ans.first,ans.second); } int neighbor(int v) { v--; if (curr[v] == 1) update(v,0,-1e9); else if (curr[v] == 2) update(v,-1e9,0); curr[v] = 0; pii ans = query(0); return min(ans.first,ans.second); }

Compilation message (stderr)

catdog.cpp: In function 'int doDFS(int, int, int)':
catdog.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
catdog.cpp: In function 'int doHLD(int, int)':
catdog.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...