oj.uz

답안 #210410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210410 2020-03-17T10:03:12 Z dennisstar Cats or Dogs (JOI18_catdog) C++17
0 / 100
 11 ms 9208 KB 
#include "catdog.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MX = 100005, INF = 3<<19;

struct node {
	int v[2][2];
	node() { for (int i=0; i<2; i++) v[i][i]=0, v[i][i^1]=INF; }
	node(int c, int d) { v[0][0]=c, v[0][1]=v[1][0]=INF, v[1][1]=d; }
};

node operator + (const node &n1, const node &n2) {
	node r;
	for (int i=0; i<2; i++) for (int j=0; j<2; j++) {
		r.v[i][j]=INF;
		for (int k=0; k<2; k++) for (int l=0; l<2; l++)
			r.v[i][j]=min(r.v[i][j], n1.v[i][k]+n2.v[l][j]+(k^l));
	}
	return r;
}

int N, Q, dep[MX], sz[MX];
int C[MX], D[MX], T[MX], out;
int in[MX], hld[MX], hla[MX];
vector<int> adj[MX], spt[MX];

node st[1<<18];
void upd(int i, int s, int e, int t, int c, int d) {
	if (s==e) { st[i]=node(c, d); return ; }
	int md=(s+e)/2;
	if (t<=md) upd(i*2, s, md, t, c, d);
	else upd(i*2+1, md+1, e, t, c, d);
	st[i]=st[i*2]+st[i*2+1];
}
node get(int i, int s, int e, int ts, int te) {
	if (e<ts||te<s) return node();
	if (ts<=s&&e<=te) return st[i];
	int md=(s+e)/2;
	return get(i*2, s, md, ts, te)+get(i*2+1, md+1, e, ts, te);
}

void dfs(int n, int p) {
	dep[n]=dep[p]+1; sz[n]=1; spt[n].eb(p);
	for (int i=0; i<spt[spt[n][i]].size(); i++) spt[n].eb(spt[spt[n][i]][i]);
	for (auto &i:adj[n]) if (i!=p) dfs(i, n), sz[n]+=sz[i];
}
int t1, t2;
void bhld(int n, int p) {
	in[n]=++t1;
	if (!hld[n]) hld[n]=++t2, hla[n]=n;
	for (auto &i:adj[n]) if (i!=p&&sz[n]<sz[i]*2) hld[i]=hld[n], hla[i]=hla[n], bhld(i, n);
	for (auto &i:adj[n]) if (i!=p&&sz[n]>=sz[i]*2) bhld(i, n);
}

void upd(int v, int c, int d) {
	if (!v) return ;

	int hla=::hla[v], hlp=spt[hla][0];
	node nd; int cc, dd;

	nd=get(1, 1, N, in[hla], in[v]);
	cc=min(nd.v[0][0], nd.v[0][1]), dd=min(nd.v[1][0], nd.v[1][1]);
	C[hlp]-=min(cc, dd+1), D[hlp]-=min(cc+1, dd);

	upd(1, 1, N, in[v], c, d);

	nd=get(1, 1, N, in[hla], in[v]);
	cc=min(nd.v[0][0], nd.v[0][1]), dd=min(nd.v[1][0], nd.v[1][1]);
	C[hlp]+=min(cc, dd+1), D[hlp]+=min(cc+1, dd);
	
	upd(hlp, T[hlp]&1?C[hlp]:INF, T[hlp]&2?D[hlp]:INF);
}

void initialize(int N, vector<int> A, vector<int> B) {
	::N=N;
	for (int i=0; i<N-1; i++) adj[A[i]].eb(B[i]), adj[B[i]].eb(A[i]);
	dfs(1, 0); bhld(1, 0); fill(T+1, T+N+1, 3);
	for (int i=1; i<=N; i++) if (hld[i]==1) out=max(out, in[i]);
}

int getans() {
	node nd=get(1, 1, N, 1, out);
	int c=min(nd.v[0][0], nd.v[0][1]), d=min(nd.v[1][0], nd.v[1][1]);
	return min(T[1]&1?c:INF, T[1]&2?d:INF);
}

int cat(int v) {
	T[v]=1;
	upd(v, C[v], INF);
	return getans();
}

int dog(int v) {
	T[v]=2;
	upd(v, INF, D[v]);
	return getans();
}

int neighbor(int v) {
	T[v]=3;
	upd(v, C[v], D[v]);
	return getans();
}

Compilation message

catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<spt[spt[n][i]].size(); i++) spt[n].eb(spt[spt[n][i]][i]);
                ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9080 KB Output is correct
2 Correct 10 ms 9084 KB Output is correct
3 Correct 11 ms 9080 KB Output is correct
4 Incorrect 10 ms 9208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9080 KB Output is correct
2 Correct 10 ms 9084 KB Output is correct
3 Correct 11 ms 9080 KB Output is correct
4 Incorrect 10 ms 9208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9080 KB Output is correct
2 Correct 10 ms 9084 KB Output is correct
3 Correct 11 ms 9080 KB Output is correct
4 Incorrect 10 ms 9208 KB Output isn't correct
5 Halted 0 ms 0 KB -