Submission #307349

#	Time	Username	Problem	Language	Result	Execution time	Memory
307349		limabeans	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3078 ms	10336 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

void setmin(int &x, int y) {
    x = min(x, y);
}

const int maxn = 2e5+10;
const int inf = 1e7;

struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};

const int NONE = 1;
const int CAT = 2;
const int DOG = 3;


int n;
vector<int> g[maxn];
vector<pair<int,int>> edges;
int state[maxn];

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for (int i=0; i<n-1; i++) {
	int u = A[i];
	int v = B[i];
	u--; v--;
	assert(u>=0 && v>=0); // assume given to us 1-indexed
	assert(u<n && v<n);
	
	g[u].push_back(v);
	g[v].push_back(u);
	edges.push_back({u,v});
    }
    for (int i=0; i<n; i++) {
	state[i] = NONE;
    }
}


void print() {
    return;
    for (int i=0; i<n; i++) {
	cout<<state[i]<<" ";
    }
    cout<<endl;
}

int brute() {
    int res = n+10;
    for (int mask=0; mask<(1<<(n-1)); mask++) {
	dsu0 dsu;
	dsu.init(n);
	for (int j=0; j<n-1; j++) {
	    if (!(mask>>j&1)) {
		int u = edges[j].first;
		int v = edges[j].second;
		dsu.join(u, v);
	    }
	}
	map<int,int> mp;

	bool ok = true;
	
	for (int i=0; i<n && ok; i++) {
	    int cc = dsu.parent(i);
	    if (state[i] == NONE) continue;
	    if (!mp.count(cc)) {
		mp[cc] = state[i];
	    }
	    if (mp[cc] != state[i]) {
		ok = false;
	    }
	}

	if (ok) {
	    int rm = __builtin_popcount(mask);
	    res = min(res, rm);
	}
    }
    return res;
}



int dp[maxn][4];

void dfs(int at, int p) {
    if (state[at] == NONE) {
	dp[at][NONE] = 0;
	dp[at][CAT] = 0;
	dp[at][DOG] = 0;
    } else {
	dp[at][NONE] = inf;
	dp[at][CAT] = inf;
	dp[at][DOG] = inf;
	dp[at][state[at]] = 0;
    }
    
    for (int to: g[at]) {
	if (to == p) {
	    continue;
	}
	dfs(to, at);
	if (state[at] == NONE) {
	    dp[at][NONE] += min({dp[to][NONE], 1+dp[to][CAT], 1+dp[to][DOG]});
	    dp[at][CAT] += min({dp[to][NONE], dp[to][CAT], 1+dp[to][DOG]});
	    dp[at][DOG] += min({dp[to][NONE], 1+dp[to][CAT], dp[to][DOG]});
	} else {
	    int cur = state[at];
	    int other = cur^CAT^DOG;
	    dp[at][state[at]] += min({dp[to][NONE], dp[to][cur], 1+dp[to][other]});
	}
    }
}

int solve() {
    for (int i=0; i<=n+2; i++) {
	for (int j=0; j<4; j++) {
	    dp[i][j] = inf;
	}
    }

    dfs(0, -1);
    int res = min({dp[0][NONE], dp[0][CAT], dp[0][DOG]});
    assert(res < inf);
    return res;
}

int cat(int v) {
    v--;
    state[v] = CAT;
    print();
    return solve();
}

int dog(int v) {
    v--;
    state[v] = DOG;
    print();
    return solve();
}

int neighbor(int v) {
    v--;
    state[v] = NONE;
    print();
    return solve();
}

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