Submission #47869

#	Time	Username	Problem	Language	Result	Execution time	Memory
47869		leejseo	트리 (KOI16_tree)	C++17	100 / 100	397 ms	65536 KiB

tree

#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 200000

int N, Q;
int par[MAXN+5];
int color[MAXN+5];
vector<int> stack1;
vector<int> stack2;
vector<int> L1;
vector<int> L2;
vector<int> dec[MAXN+5];
bool vis[MAXN+5];
int cc = 1;

void input(){
	scanf("%d%d", &N, &Q);
	par[1] = -1;
	par[0] = -1;
	color[1] = 1;
	for (int i=2; i<=N; i++){
		color[i] = 1;
		scanf("%d", &par[i]);
		dec[par[i]].push_back(i);
	}
}

void delete_edge(int u){
	if (u == 1) return;
	if (par[u] == -1) return;
	if (color[u] != color[par[u]]) return;
	for (int i=0; i<L1.size(); i++){
		vis[L1[i]] = false;
	}
	for (int i=0; i<L2.size(); i++){
		vis[L2[i]] = false;
	}
	L1.clear();
	L2.clear();
	stack1.clear();
	stack2.clear();
	L1.push_back(par[u]);
	stack1.push_back(par[u]);
	L2.push_back(u);
	stack2.push_back(u);
	par[u] = -1;
	while ((stack1.size() >= 1) && (stack2.size() >= 1)){
		int v1 = stack1.back();
		int v2 = stack2.back();
		stack1.pop_back();
		stack2.pop_back();
		vis[v1] = true;
		vis[v2] = true;
		if ((par[v1] == -1) && (dec[v1].empty()) && (stack1.empty())){
			break;
		}
		if ((dec[v2].empty()) && (stack2.empty())) {
			stack1.push_back(1);
			break;		
		}
		//for stack1
		if (par[v1] != -1) {
			if ((color[par[v1]] == color[v1]) && (!vis[par[v1]])){
				stack1.push_back(par[v1]);
				L1.push_back(par[v1]);
			}
		}
		if (dec[v1].size() > 0){
			for (int i=0; i<dec[v1].size(); i++){
				int w = dec[v1][i];
				if ((color[w] == color[v1]) && (!vis[w])){
					L1.push_back(w);
					stack1.push_back(w);
				}
			}
		}
		// for stack2
		if (dec[v2].size() > 0){
			for (int i=0; i<dec[v2].size(); i++){
				int w = dec[v2][i];
				if ((color[w] == color[v2]) && (!vis[w])){
					L2.push_back(w);
					stack2.push_back(w);
				}
			}
		}
	}
	if (stack1.empty()){
		// connected component w/ parent is smaller
		for (int i=0; i<L1.size(); i++){
			color[L1[i]] = cc + 1;
		}
	}
	else{
		// connected component w/ u is smaller
		for (int i=0; i<L2.size(); i++){
			color[L2[i]] = cc + 1;
		}
	}
	cc += 1;
}

//Deal with query

int main(void){
	input();
	for (int query=0; query<Q; query++){
		int u, v, q;
		scanf("%d%d%d", &u, &v, &q);
		if (color[u] == color[v]){
			printf("YES\n");
			if (q) delete_edge(u);
		}
		else{
			printf("NO\n");
			if (q) delete_edge(v);
		}
	}
}

Compilation message (stderr)

tree.cpp: In function 'void delete_edge(int)':
tree.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<L1.size(); i++){
                ~^~~~~~~~~~
tree.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<L2.size(); i++){
                ~^~~~~~~~~~
tree.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<dec[v1].size(); i++){
                  ~^~~~~~~~~~~~~~~
tree.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<dec[v2].size(); i++){
                  ~^~~~~~~~~~~~~~~
tree.cpp:93:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<L1.size(); i++){
                 ~^~~~~~~~~~
tree.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<L2.size(); i++){
                 ~^~~~~~~~~~
tree.cpp: In function 'void input()':
tree.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
tree.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &par[i]);
   ~~~~~^~~~~~~~~~~~~~~
tree.cpp: In function 'int main()':
tree.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45