답안 #421329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421329 2021-06-09T04:00:25 Z 송준혁(#7507) Cats or Dogs (JOI18_catdog) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int A[101010], C[101010], D[101010];
vector<int> adj[101010];
int I[101010], Pa[101010], num;
int L[101010], R[101010];
int P[101010], W[101010];

struct Node{
	int cc, cd, dc, dd;
	Node(){cc=dd=0, cd=dc=1;}
	void trm(){
		cc = min(cc, cd+1), cc = min(cc, dc+1), cc = min(cc, dd+2);
		cd = min(cd, cc+1), cd = min(cd, dd+1), cd = min(cd, dc+2);
		dc = min(dc, cc+1), dc = min(dc, dd+1), dc = min(dc, cd+2);
		dd = min(dd, cd+1), dd = min(dd, dc+1), dd = min(dd, cc+2);
	}
	Node operator+(const Node &r)const{
		Node ret;
		ret.cc = min(cc+r.cc, cd+r.dc);
		ret.cd = min(cc+r.cd, cd+r.dd);
		ret.dc = min(dc+r.cc, dd+r.dc);
		ret.dd = min(dc+r.cd, dd+r.dd);
		ret.trm();
		return ret;
	}
} T[404040];

void dfs(int u, int p){
	W[u] = 1, Pa[u] = p;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u), W[u]+=W[v];
	}
	sort(adj[u].begin(), adj[u].end(), [&](int a, int b){
		if (a == p) return false;
		if (b == p) return true;
		return W[a] > W[b];
	});
	if (u>1) adj[u].pop_back();
}

void hld(int u, int r){
	I[u] = ++num, L[I[u]] = I[r], R[I[r]] = I[u];
	if (!adj[u].size()) return;
	hld(adj[u][0], r);
	for (int i=1; i<adj[u].size(); i++) hld(adj[u][i], adj[u][i]);
}

void upd(int id, int s, int e, int t){
	if (e < t || t < s) return;
	if (s == e){
		T[id].cc=T[id].cd=T[id].dc=T[id].dd=N;
		if (A[t] != 1) T[id].dd=D[t];
		if (A[t] != 2) T[id].cc=C[t];
		T[id].trm();
		return;
	}
	int m=s+e>>1;
	upd(id*2, s, m, t), upd(id*2+1, m+1, e, t);
	T[id] = T[id*2] + T[id*2+1];
}

Node sum(int id, int s, int e, int ts, int te){
	if (e < ts || te < s) return Node();
	if (ts <= s && e <= te) return T[id];
	int m=s+e>>1;
	return sum(id*2, s, m, ts, te)+sum(id*2+1, m+1, e, ts, te);
}

int main(){
	Node t;
	scanf("%d", &N);
	for (int i=1; i<N; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].pb(v), adj[v].pb(u);
	}
	dfs(1, 0), hld(1, 1);
	for (int i=1; i<=N; i++) P[I[i]] = I[Pa[i]];
	scanf("%d", &Q);
	while (Q--){
		int u, x;
		scanf("%d %d", &x, &u);
		u = I[u], A[u] = x;
		while (u){
			t = sum(1, 1, N, L[u], R[L[u]]);
			C[P[L[u]]] -= min(t.cc, t.cd);
			D[P[L[u]]] -= min(t.dc, t.dd);
			upd(1, 1, N, u);
			t = sum(1, 1, N, L[u], R[L[u]]);
			C[P[L[u]]] += min(t.cc, t.cd);
			D[P[L[u]]] += min(t.dc, t.dd);
			u = P[L[u]];
		}
		printf("%d\n", min(C[0], D[0]));
	}
	return 0;
}

Compilation message

catdog.cpp: In function 'void hld(int, int)':
catdog.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i=1; i<adj[u].size(); i++) hld(adj[u][i], adj[u][i]);
      |                ~^~~~~~~~~~~~~~
catdog.cpp: In function 'void upd(int, int, int, int)':
catdog.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |  int m=s+e>>1;
      |        ~^~
catdog.cpp: In function 'Node sum(int, int, int, int, int)':
catdog.cpp:77:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int m=s+e>>1;
      |        ~^~
catdog.cpp: In function 'int main()':
catdog.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
catdog.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
catdog.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
catdog.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d %d", &x, &u);
      |   ~~~~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccEjUbG8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDKx5M9.o:catdog.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEjUbG8.o: in function `main':
grader.cpp:(.text.startup+0x1e2): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x219): undefined reference to `neighbor(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x25e): undefined reference to `dog(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x269): undefined reference to `cat(int)'
collect2: error: ld returned 1 exit status