oj.uz

Submission #111690

# Submission time Handle Problem Language Result Execution time Memory
111690 2019-05-16T02:09:51 Z gs14004 Cats or Dogs (JOI18_catdog) C++17
100 / 100
 1681 ms 28904 KB 
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXT = 270000;
const int inf = 1e9;

int n, a[MAXN];
vector<int> gph[MAXN];
int sz[MAXN], chn[MAXN], csz[MAXN], dfn[MAXN], par[MAXN], piv;

int slack[MAXN][3];

struct mtrx{
	int a[3][3];
}E;

mtrx mul(mtrx a, mtrx b){
	mtrx c; memset(c.a, 0x3f, sizeof(c.a));
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			for(int k=0; k<3; k++){
				c.a[j][k] = min(a.a[j][i] + b.a[i][k], c.a[j][k]);
			}
		}
	}
	return c;
}

struct seg{
	int lim;
	mtrx tree[MAXT];
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=0; i<MAXT; i++){
			tree[i] = E;
		}
	}
	void add(int x, mtrx v){
		x += lim;
		tree[x] = v;
		while(x > 1){
			x >>= 1;
			tree[x] = mul(tree[2*x], tree[2*x+1]);
		}
	}
	mtrx query(int s, int e){
		s += lim;
		e += lim;
		mtrx lmtrx = E, rmtrx = E;
		while(s < e){
			if(s%2 == 1) lmtrx = mul(lmtrx, tree[s++]); 
			if(e%2 == 0) rmtrx = mul(tree[e--], rmtrx);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) rmtrx = mul(tree[s], rmtrx);
		return mul(lmtrx, rmtrx);
	}	
}seg;

vector<int> line_query(int s, int e){
	auto quer = seg.query(s, e);
	vector<int> nxt(3);
	for(int i=0; i<3; i++){
		nxt[i]  = 1e9;
		for(int j=0; j<3; j++) nxt[i] = min(nxt[i], quer.a[i][j]);
	}
	return nxt;
}

void slack_update(int v){
	mtrx m;
	m.a[0][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[0][1] = slack[v][1] + 1 + (a[v] == 2 ? inf : 0);
	m.a[0][2] = slack[v][2] + 1 + (a[v] == 1 ? inf : 0);

	m.a[1][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[1][1] = slack[v][1] + 0 + (a[v] == 2 ? inf : 0);
	m.a[1][2] = slack[v][2] + 1 + (a[v] == 1 ? inf : 0);

	m.a[2][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[2][1] = slack[v][1] + 1 + (a[v] == 2 ? inf : 0);
	m.a[2][2] = slack[v][2] + 0 + (a[v] == 1 ? inf : 0);

	seg.add(v, m);
}

void Do(int v, int w){
	vector<int> pth;
	for(int i = v; i; i = par[chn[i]]){
		pth.push_back(i);
	}
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] -= queryV[0];
		slack[parV][1] -= queryV[1];
		slack[parV][2] -= queryV[2];
		if(parV) slack_update(parV);
	}
	a[dfn[v]] = w;
	slack_update(dfn[v]);
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] += queryV[0];
		slack[parV][1] += queryV[1];
		slack[parV][2] += queryV[2];
		if(parV) slack_update(parV);
	}
}

int cat(int v) {
	Do(v, 1);
	return *min_element(slack[0], slack[0] + 3);
}

int dog(int v) {
	Do(v, 2);
	return *min_element(slack[0], slack[0] + 3);
}

int neighbor(int v) {
	Do(v, 0);
	return *min_element(slack[0], slack[0] + 3);
}

void dfs(int x){
	sz[x] = 1;
	for(auto &i : gph[x]){
		gph[i].erase(find(gph[i].begin(), gph[i].end(), x));
		par[i] = x;
		dfs(i);
		sz[x] += sz[i];
	}
	sort(gph[x].begin(), gph[x].end(), [&](const int &a, const int &b){
		return sz[a] > sz[b];
	});
}

void hld(int x){
	dfn[x] = ++piv;
	csz[chn[x]]++;
	if(gph[x].empty()) return;
	chn[gph[x][0]] = chn[x];
	hld(gph[x][0]);
	for(int i=1; i<gph[x].size(); i++){
		chn[gph[x][i]] = gph[x][i];
		hld(gph[x][i]);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	for(int i=0; i<n-1; i++){
		gph[A[i]].push_back(B[i]);
		gph[B[i]].push_back(A[i]);
	}
	dfs(1);
	chn[1] = 1;
	hld(1);
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			E.a[i][j] = (i == j ? 0 : 1e9);
		}
	}
	seg.init(n);
}

Compilation message

catdog.cpp: In function 'void hld(int)':
catdog.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<gph[x].size(); i++){
               ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 13 ms 12288 KB Output is correct
6 Correct 11 ms 12304 KB Output is correct
7 Correct 11 ms 12288 KB Output is correct
8 Correct 11 ms 12288 KB Output is correct
9 Correct 11 ms 12288 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 12 ms 12160 KB Output is correct
12 Correct 13 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12160 KB Output is correct
15 Correct 13 ms 12160 KB Output is correct
16 Correct 13 ms 12288 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 13 ms 12288 KB Output is correct
6 Correct 11 ms 12304 KB Output is correct
7 Correct 11 ms 12288 KB Output is correct
8 Correct 11 ms 12288 KB Output is correct
9 Correct 11 ms 12288 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 12 ms 12160 KB Output is correct
12 Correct 13 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12160 KB Output is correct
15 Correct 13 ms 12160 KB Output is correct
16 Correct 13 ms 12288 KB Output is correct
17 Correct 16 ms 12288 KB Output is correct
18 Correct 14 ms 12288 KB Output is correct
19 Correct 12 ms 12288 KB Output is correct
20 Correct 13 ms 12288 KB Output is correct
21 Correct 14 ms 12288 KB Output is correct
22 Correct 12 ms 12288 KB Output is correct
23 Correct 17 ms 12288 KB Output is correct
24 Correct 17 ms 12288 KB Output is correct
25 Correct 16 ms 12288 KB Output is correct
26 Correct 15 ms 12288 KB Output is correct
27 Correct 18 ms 12288 KB Output is correct
28 Correct 14 ms 12284 KB Output is correct
29 Correct 16 ms 12288 KB Output is correct
30 Correct 14 ms 12288 KB Output is correct
31 Correct 15 ms 12288 KB Output is correct
32 Correct 15 ms 12288 KB Output is correct

Subtask #3
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 13 ms 12288 KB Output is correct
6 Correct 11 ms 12304 KB Output is correct
7 Correct 11 ms 12288 KB Output is correct
8 Correct 11 ms 12288 KB Output is correct
9 Correct 11 ms 12288 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 12 ms 12160 KB Output is correct
12 Correct 13 ms 12288 KB Output is correct
13 Correct 11 ms 12288 KB Output is correct
14 Correct 11 ms 12160 KB Output is correct
15 Correct 13 ms 12160 KB Output is correct
16 Correct 13 ms 12288 KB Output is correct
17 Correct 16 ms 12288 KB Output is correct
18 Correct 14 ms 12288 KB Output is correct
19 Correct 12 ms 12288 KB Output is correct
20 Correct 13 ms 12288 KB Output is correct
21 Correct 14 ms 12288 KB Output is correct
22 Correct 12 ms 12288 KB Output is correct
23 Correct 17 ms 12288 KB Output is correct
24 Correct 17 ms 12288 KB Output is correct
25 Correct 16 ms 12288 KB Output is correct
26 Correct 15 ms 12288 KB Output is correct
27 Correct 18 ms 12288 KB Output is correct
28 Correct 14 ms 12284 KB Output is correct
29 Correct 16 ms 12288 KB Output is correct
30 Correct 14 ms 12288 KB Output is correct
31 Correct 15 ms 12288 KB Output is correct
32 Correct 15 ms 12288 KB Output is correct
33 Correct 929 ms 17868 KB Output is correct
34 Correct 263 ms 18012 KB Output is correct
35 Correct 859 ms 16880 KB Output is correct
36 Correct 1599 ms 22524 KB Output is correct
37 Correct 36 ms 15096 KB Output is correct
38 Correct 1558 ms 23384 KB Output is correct
39 Correct 1681 ms 23480 KB Output is correct
40 Correct 1556 ms 23368 KB Output is correct
41 Correct 1518 ms 23372 KB Output is correct
42 Correct 1498 ms 23364 KB Output is correct
43 Correct 1598 ms 23364 KB Output is correct
44 Correct 1394 ms 23368 KB Output is correct
45 Correct 1393 ms 23424 KB Output is correct
46 Correct 1512 ms 23372 KB Output is correct
47 Correct 1485 ms 23376 KB Output is correct
48 Correct 344 ms 19520 KB Output is correct
49 Correct 366 ms 21024 KB Output is correct
50 Correct 147 ms 14584 KB Output is correct
51 Correct 158 ms 15712 KB Output is correct
52 Correct 67 ms 14072 KB Output is correct
53 Correct 551 ms 21996 KB Output is correct
54 Correct 482 ms 16688 KB Output is correct
55 Correct 1341 ms 20496 KB Output is correct
56 Correct 763 ms 17668 KB Output is correct
57 Correct 1039 ms 21404 KB Output is correct
58 Correct 69 ms 15732 KB Output is correct
59 Correct 121 ms 15664 KB Output is correct
60 Correct 255 ms 20248 KB Output is correct
61 Correct 350 ms 20820 KB Output is correct
62 Correct 195 ms 18644 KB Output is correct
63 Correct 118 ms 19064 KB Output is correct
64 Correct 117 ms 20680 KB Output is correct
65 Correct 155 ms 25316 KB Output is correct
66 Correct 214 ms 15864 KB Output is correct
67 Correct 201 ms 21624 KB Output is correct
68 Correct 423 ms 25720 KB Output is correct
69 Correct 97 ms 13816 KB Output is correct
70 Correct 28 ms 12536 KB Output is correct
71 Correct 143 ms 18752 KB Output is correct
72 Correct 242 ms 23900 KB Output is correct
73 Correct 648 ms 28904 KB Output is correct
74 Correct 662 ms 25336 KB Output is correct
75 Correct 429 ms 28792 KB Output is correct
76 Correct 431 ms 27612 KB Output is correct
77 Correct 734 ms 25720 KB Output is correct