Submission #210404

# Submission time Handle Problem Language Result Execution time Memory
210404 2020-03-17T09:55:59 Z dennisstar Cats or Dogs (JOI18_catdog) C++17
Compilation error
0 ms 0 KB
#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];
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);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>N;
	for (int i=1, u, v; i<N; i++) cin>>u>>v, adj[u].eb(v), adj[v].eb(u);
	dfs(1, 0); bhld(1, 0); fill(T+1, T+N+1, 3);
	int out=0;
	for (int i=1; i<=N; i++) if (hld[i]==1) out=max(out, in[i]);
	cin>>Q; while (Q--) {
		int q, v;
		cin>>q>>v;
		T[v]=q;
		upd(v, q&1?C[v]:INF, q&2?D[v]:INF);

		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]);
		cout<<min(T[1]&1?c:INF, T[1]&2?d:INF)<<'\n';
	}
	return 0;
}

Compilation message

catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:45: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]);
                ~^~~~~~~~~~~~~~~~~~~~~~
/tmp/ccEJqmyD.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXjx2uk.o:catdog.cpp:(.text.startup+0x0): first defined here
/tmp/ccEJqmyD.o: In function `main':
grader.cpp:(.text.startup+0x14f): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
grader.cpp:(.text.startup+0x1a9): undefined reference to `neighbor(int)'
grader.cpp:(.text.startup+0x1e2): undefined reference to `dog(int)'
grader.cpp:(.text.startup+0x1f1): undefined reference to `cat(int)'
collect2: error: ld returned 1 exit status