Submission #20826

#	Time	Username	Problem	Language	Result	Execution time	Memory
20826		model_code	트리 (KOI16_treeM)	C++11	100 / 100	1169 ms	20280 KiB

tree

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

#define MAX 200100

using namespace std;

struct xy {
int x, y;
};

int labelw;
int label[MAX];
vector<xy>edge[MAX];

deque<int>st1;
bool is_gone[MAX];

int cut1, cut2;
int parent[MAX];
int ep1[MAX];
int ep2[MAX];

void un_check(int w) {
int i;
is_gone[w] = 0;
for (i = 0; i < edge[w].size(); i++) {
if (is_gone[edge[w][i].x] == 0)
continue;
un_check(edge[w][i].x);
}
}

void labeling(int w) {
int i;
is_gone[w] = 1;
label[w] = labelw;
for (i = 0; i < edge[w].size(); i++) {
if (edge[w][i].y == 1)
continue;
if (is_gone[edge[w][i].x])
continue;
labeling(edge[w][i].x);
}
}
vector<int>stw[2];
vector<int>sti[2];


int main() {
int n, q;
int i, j;
int a, b;
int P;
int flag;
int noww, nowi;

scanf("%d%d", &n, &q);
labelw = 1;
for (i = 1; i <= n; i++) {
label[i] = labelw;
}
labelw++;

parent[1] = -1;

for (i = 2; i <= n; i++) {
scanf("%d", &parent[i]);
ep1[i] = edge[i].size();
ep2[i] = edge[parent[i]].size();
edge[parent[i]].push_back({ i, 0 });
edge[i].push_back({ parent[i], 0 });
}

for (i = 0; i < n + q - 1; i++) {
scanf("%d", &flag);
if (flag == 1) {
scanf("%d%d", &a, &b);
if (label[a] == label[b]) {
printf("YES\n");
}
else {
printf("NO\n");
}
continue;
}
scanf("%d", &cut1);
cut2 = parent[cut1];
if (cut2 == -1)
continue;
edge[cut1][ep1[cut1]].y = 1;
edge[cut2][ep2[cut1]].y = 1;
stw[0].push_back(cut1); sti[0].push_back(0);
stw[1].push_back(cut2); sti[1].push_back(0);
flag = 0;
while (1) {
if (stw[flag].empty())
break;
noww = stw[flag].back();
nowi = sti[flag].back();
stw[flag].pop_back();
sti[flag].pop_back();
is_gone[noww] = 1;
while (1) {
if (nowi == edge[noww].size())
break;
if (edge[noww][nowi].y) {
nowi++;
continue;
}
if (is_gone[edge[noww][nowi].x]) {
nowi++;
continue;
}
break;
}
if (nowi == edge[noww].size()) {
continue;
}
stw[flag].push_back(noww);
sti[flag].push_back(nowi + 1);
stw[flag].push_back(edge[noww][nowi].x);
sti[flag].push_back(0);
flag = !flag;
}
stw[0].clear(); sti[0].clear();
stw[1].clear(); sti[1].clear();
un_check(cut1);
if (flag == 0) {
labeling(cut1);
labelw++;
un_check(cut1);
}
else {
labeling(cut2);
labelw++;
un_check(cut2);
}
}

return 0;
}

Compilation message (stderr)

tree.cpp: In function 'void un_check(int)':
tree.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (i = 0; i < edge[w].size(); i++) {
               ^
tree.cpp: In function 'void labeling(int)':
tree.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (i = 0; i < edge[w].size(); i++) {
               ^
tree.cpp: In function 'int main()':
tree.cpp:106:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (nowi == edge[noww].size())
          ^
tree.cpp:118:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (nowi == edge[noww].size()) {
          ^
tree.cpp:53:8: warning: unused variable 'j' [-Wunused-variable]
 int i, j;
        ^
tree.cpp:55:5: warning: unused variable 'P' [-Wunused-variable]
 int P;
     ^
tree.cpp:59:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d", &n, &q);
                      ^
tree.cpp:69:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &parent[i]);
                        ^
tree.cpp:77:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &flag);
                   ^
tree.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d", &a, &b);
                      ^
tree.cpp:88:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &cut1);
                   ^

• Subtask 1: 22 / 22
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 29 / 29