oj.uz

Submission #307342

# Submission time Handle Problem Language Result Execution time Memory
307342 2020-09-27T22:38:14 Z limabeans Cats or Dogs (JOI18_catdog) C++17
8 / 100
 1136 ms 23932 KB 
#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;

const int maxn = 1e6 + 5;

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 = 0;
const int DOG = 1;


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 solve() {
    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 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 442 ms 23868 KB Output is correct
4 Correct 26 ms 23808 KB Output is correct
5 Correct 59 ms 23808 KB Output is correct
6 Correct 918 ms 23928 KB Output is correct
7 Correct 1043 ms 23928 KB Output is correct
8 Correct 1136 ms 23928 KB Output is correct
9 Correct 978 ms 23856 KB Output is correct
10 Correct 932 ms 23932 KB Output is correct
11 Correct 622 ms 23928 KB Output is correct
12 Correct 16 ms 23808 KB Output is correct
13 Correct 15 ms 23800 KB Output is correct
14 Correct 15 ms 23808 KB Output is correct
15 Correct 15 ms 23808 KB Output is correct
16 Correct 417 ms 23928 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 442 ms 23868 KB Output is correct
4 Correct 26 ms 23808 KB Output is correct
5 Correct 59 ms 23808 KB Output is correct
6 Correct 918 ms 23928 KB Output is correct
7 Correct 1043 ms 23928 KB Output is correct
8 Correct 1136 ms 23928 KB Output is correct
9 Correct 978 ms 23856 KB Output is correct
10 Correct 932 ms 23932 KB Output is correct
11 Correct 622 ms 23928 KB Output is correct
12 Correct 16 ms 23808 KB Output is correct
13 Correct 15 ms 23800 KB Output is correct
14 Correct 15 ms 23808 KB Output is correct
15 Correct 15 ms 23808 KB Output is correct
16 Correct 417 ms 23928 KB Output is correct
17 Incorrect 88 ms 23808 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 442 ms 23868 KB Output is correct
4 Correct 26 ms 23808 KB Output is correct
5 Correct 59 ms 23808 KB Output is correct
6 Correct 918 ms 23928 KB Output is correct
7 Correct 1043 ms 23928 KB Output is correct
8 Correct 1136 ms 23928 KB Output is correct
9 Correct 978 ms 23856 KB Output is correct
10 Correct 932 ms 23932 KB Output is correct
11 Correct 622 ms 23928 KB Output is correct
12 Correct 16 ms 23808 KB Output is correct
13 Correct 15 ms 23800 KB Output is correct
14 Correct 15 ms 23808 KB Output is correct
15 Correct 15 ms 23808 KB Output is correct
16 Correct 417 ms 23928 KB Output is correct
17 Incorrect 88 ms 23808 KB Output isn't correct
18 Halted 0 ms 0 KB -