Submission #62289

#	Time	Username	Problem	Language	Result	Execution time	Memory
62289		kriii	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	544 ms	89044 KiB

catdog

#include "catdog.h"
#include <algorithm>
using namespace std;

int N;
vector<int> G[100100]; int P[100100];

const int inf = 1000000000;
struct mat{
	mat(long long a, long long b)
	{
		if (a > inf) a = inf;
		if (b > inf) b = inf;
		A[0][0] = a; A[0][1] = a+1;
		A[1][0] = b+1; A[1][1] = b;
	}
	mat()
	{
		A[0][0] = 0; A[0][1] = 1;
		A[1][0] = 1; A[1][1] = 0;
	}
	int A[2][2];

	mat operator *(const mat &t) const{
		mat r(0,0);
		for (int i=0;i<2;i++) for (int j=0;j<2;j++){
			r.A[i][j] = inf;
			for (int k=0;k<2;k++){
				r.A[i][j] = min(r.A[i][j],A[i][k]+t.A[k][j]);
			}
		}
		return r;
	};
};

vector<int> see;
int go(int x, int l)
{
	see.push_back(x);

	P[x] = l;
	auto I = find(G[x].begin(),G[x].end(),l);
	if (I != G[x].end()) G[x].erase(I);

	int sz = 1, mx = 0, v;
	for (auto &y : G[x]){
		int z = go(y,x);
		sz += z;
		if (mx < z)
			mx = z, v = y;
	}

	if (mx){
		auto J = find(G[x].begin(),G[x].end(),v);
		swap(G[x][0],*J);
	}

	return sz;
}

int C,num[100100],pos[100100],sz[100100],pw[100100],la[100100],lb[100100];
vector<long long> chain[100100],addA[100100],addB[100100];
vector<mat> IT[100100];

void initialize(int N_, std::vector<int> A, std::vector<int> B) {
	N = N_;
	for (int i=0;i<A.size();i++){
		int x = A[i], y = B[i];
		G[x].push_back(y);
		G[y].push_back(x);
	}
	go(1,0);

	C++;
	for (int &i : see){
		if (G[i].empty()) continue;
		int x = G[i][0];
		num[x] = num[i];
		for (int j=1;j<G[i].size();j++){
			int y = G[i][j];
			num[y] = C++;
		}
	}
	for (int &i : see){
		pos[i] = sz[num[i]]++;
		chain[num[i]].push_back(i);
	}

	for (int i=0;i<C;i++){
		addA[i].resize(sz[i]);
		addB[i].resize(sz[i]);
		pw[i] = 1;
		while (pw[i] < sz[i]) pw[i] *= 2;
		IT[i].resize(pw[i]*2);
	}
}

void up(vector<mat> &it, int Z, int x, mat t)
{
	x += Z;
	it[x] = t; x /= 2;
	while (x){
		it[x] = it[x*2] * it[x*2+1];
		x /= 2;
	}
}

void push(int x, int a, int b)
{
	bool f = true;
	while (x){
		int n = num[x];
		int v = chain[n][0];
		int p = P[v];
		if (p){
			int A = min(IT[n][1].A[0][0],IT[n][1].A[0][1]);
			int B = min(IT[n][1].A[1][0],IT[n][1].A[1][1]);
			int np = num[p];
			addA[np][pos[p]] -= min(A,B+1);
			addB[np][pos[p]] -= min(A+1,B);
		}

		int ps = pos[x];
		if (f){
			addA[n][ps] -= la[x];
			addB[n][ps] -= lb[x];
			la[x] = a;
			lb[x] = b;
			addA[n][ps] += a;
			addB[n][ps] += b;
			f = 0;
		}
		up(IT[n], pw[n], ps, mat(addA[n][ps],addB[n][ps]));

		if (p){
			int A = min(IT[n][1].A[0][0],IT[n][1].A[0][1]);
			int B = min(IT[n][1].A[1][0],IT[n][1].A[1][1]);
			int np = num[p];
			addA[np][pos[p]] += min(A,B+1);
			addB[np][pos[p]] += min(A+1,B);
		}

		x = p;
	}
}

int getV()
{
	return min({IT[0][1].A[0][0],IT[0][1].A[0][1],IT[0][1].A[1][0],IT[0][1].A[1][1]});
}

int cat(int v) {
	push(v, 0, inf);
	return getV();
}

int dog(int v) {
	push(v, inf ,0);
	return getV();
}

int neighbor(int v) {
	push(v, 0, 0);
	return getV();
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<A.size();i++){
               ~^~~~~~~~~
catdog.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1;j<G[i].size();j++){
                ~^~~~~~~~~~~~

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