Submission #61388

#	Time	Username	Problem	Language	Result	Execution time	Memory
61388		egorlifar	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	512 ms	136088 KiB

catdog

#include "catdog.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
const long long inf = 1e16;
const int MAXN = 1000228, MAXNN = 100228;

 
struct node {
  long long val[2][2];
  node(){
    val[0][0] = val[1][1] = 0, val[0][1] = val[1][0] = inf;
  }
  node operator+(const node &p) const{
    node ret;
    for(int i=0; i<2; i++)
      for(int j=0; j<2; j++){
        ret.val[i][j] = inf;
        for(int k=0; k<2; k++)
          for(int l=0; l<2; l++)
            ret.val[i][j] = min(ret.val[i][j], val[i][k] + p.val[l][j] + (k ^ l));
      }
    return ret;
  }
};
 
struct segtree {
  	vector<node> val;
  	int sz;
  	void init(int root, int lo, int hi){
	    if(lo == hi) return;
	    int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
	    init(left, lo, mid);
	    init(right, mid + 1, hi);
	    val[root] = val[left] + val[right];
  	}
  	void init(int n){
	    int s = 1;
	    sz = n;
	    while(s < (sz << 1)) s <<= 1;
	    val.resize(s);
	    init(1, 1, sz);
 	}
  	void update(int root, int lo, int hi, int x, long long v0, long long v1){
	    if (lo == hi){
		    val[root].val[0][0] += v0;
		    val[root].val[1][1] += v1;
		    return;
	    }
	    int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
	    if (x <= mid) {
	    	update(left, lo, mid, x, v0, v1);
	    } else {
	    	update(right, mid + 1, hi, x, v0, v1);
	    }
	    val[root] = val[left] + val[right];
  	}
  	void update(int pos, long long x0, long long x1){
    	update(1, 1, sz, pos, x0, x1);
  	}
 	pair<int, int> query() const{
    	int x = min(val[1].val[0][0], val[1].val[0][1]);
    	int y = min(val[1].val[1][0], val[1].val[1][1]);
    	return make_pair(min(x, y + 1), min(x + 1, y));
  	}
} seg[MAXNN];
 

int n;
vector<int> edge[MAXNN];
int sz[MAXNN], pathPar[MAXNN], pathPos[MAXNN], par[MAXNN], st[MAXNN];
 

void dfsSize(int x, int p){
	par[x] = p, sz[x] = 1;
	for(auto i: edge[x]){
	    if(i == p) continue;
	    dfsSize(i, x);
	    sz[x] += sz[i];
	}
}

 
void dfsDecomp(int x, int p){
	int hpath = 0;
	for(int i : edge[x]){
	    if(i == p) continue;
	    if(sz[x] <= (sz[i] << 1)){
	        hpath = i;
	        break;
	    }
	 }
	if(hpath == 0) seg[pathPar[x]].init(pathPos[x]);
	for (int i: edge[x]){
	    if (i == p) continue;
	    if (i != hpath){
	      pathPar[i] = i;
	      pathPos[i] = 1;
	    }
	    else{
	      pathPar[i] = pathPar[x];
	      pathPos[i] = pathPos[x] + 1;
	    }
	    dfsDecomp(i, x);
	}
}
 

void initialize(int N, vector<int> A, vector<int> B) {
 	n = N;
	for (int i = 0; i < n - 1; i++) {
	    edge[A[i]].pb(B[i]);
	    edge[B[i]].pb(A[i]);
	}
  	dfsSize(1, 0);
  	pathPar[1] = 1, pathPos[1] = 1;
  	dfsDecomp(1, 0);
}

 
void update(int x, int v0, int v1) {
  	while (x) {
	    int path = pathPar[x];
	    int pr0, pr1, nx0, nx1;
	    tie(pr0, pr1) = seg[path].query();
	    seg[path].update(pathPos[x], v0, v1);
	    tie(nx0, nx1) = seg[path].query();
	    v0 = nx0 - pr0;
	    v1 = nx1 - pr1;
	    x = par[pathPar[x]];
  	}
}


int getAns() {
  	pair<int, int> it = seg[1].query();
  	return min(it.first, it.second);
}


int cat(int v) {
	st[v] = 1;
  	update(v, MAXN, 0);
  	return getAns();
}


int dog(int v) {
	st[v] = 2;
  	update(v, 0, MAXN);
  	return getAns();
}

int neighbor(int v) {
	if (st[v] == 1) {
		update(v, -MAXN, 0);
	} else {
		update(v, 0, -MAXN);
	}
  	st[v] = 0;
  	return getAns();
}

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62