Submission #20643

#	Time	Username	Problem	Language	Result	Execution time	Memory
20643		model_code	트리 (KOI16_tree)	C++11	100 / 100	849 ms	31200 KiB

tree

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

#define MAX 400100
#pragma warning(disable:4996)

using namespace std;

struct xy {
int x, y, z;
};

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

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

int cut1, cut2;
int parent[MAX];
int ep[2][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 (is_gone[edge[w][i].x]) continue;
labeling(edge[w][i].x);
}
}
vector<int>stw[2];
vector<int>sti[2];
vector<int>done;


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]);
ep[0][i] = edge[i].size();
ep[1][i] = edge[parent[i]].size();
edge[i].push_back({ parent[i], i ,0});
edge[parent[i]].push_back({ i, i ,1 });
}

for (i = 0; i < q; i++) {
scanf("%d%d%d", &a, &b, &flag);
if (flag == 0) {
if (label[a] == label[b]) printf("YES\n");
else printf("NO\n");
continue;
}
if (label[a] == label[b]) {
printf("YES\n");
cut1 = a;
cut2 = parent[a];

}
else {
printf("NO\n");
cut1 = b;
cut2 = parent[b];
}
if (cut2 == -1) continue;
if (ep[0][cut1] == -1) continue;

if (ep[0][cut1] == edge[cut1].size() - 1) edge[cut1].pop_back();
else {
edge[cut1][ep[0][cut1]] = edge[cut1].back();
edge[cut1].pop_back();
ep[edge[cut1][ep[0][cut1]].z][edge[cut1][ep[0][cut1]].y] = ep[0][cut1];
}

if (ep[1][cut1] == edge[cut2].size() - 1) edge[cut2].pop_back();
else {
edge[cut2][ep[1][cut1]] = edge[cut2].back();
edge[cut2].pop_back();
ep[edge[cut2][ep[1][cut1]].z][edge[cut2][ep[1][cut1]].y] = ep[1][cut1];
}
ep[0][cut1] = -1;
ep[1][cut1] = -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();
if(nowi==0)
done.push_back(noww);
stw[flag].pop_back();
sti[flag].pop_back();
is_gone[noww] = 1;
while (1) {
if (nowi == edge[noww].size()) break;
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;
}
for (j = 0; j < done.size(); j++) is_gone[done[j]] = 0;
done.clear();
stw[0].clear(); sti[0].clear();
stw[1].clear(); sti[1].clear();
if (flag == 0) {
labeling(cut1);
labelw++;
un_check(cut1);
}
else {
labeling(cut2);
labelw++;
un_check(cut2);
}
}

return 0;
}

Compilation message (stderr)

tree.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 ^
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:38: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:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (ep[0][cut1] == edge[cut1].size() - 1) edge[cut1].pop_back();
                 ^
tree.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (ep[1][cut1] == edge[cut2].size() - 1) edge[cut2].pop_back();
                 ^
tree.cpp:122:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (nowi == edge[noww].size()) break;
          ^
tree.cpp:129:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (nowi == edge[noww].size()) continue;
          ^
tree.cpp:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (j = 0; j < done.size(); j++) is_gone[done[j]] = 0;
               ^
tree.cpp:52:5: warning: unused variable 'P' [-Wunused-variable]
 int P;
     ^
tree.cpp:56: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:64:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &parent[i]);
                        ^
tree.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d%d", &a, &b, &flag);
                               ^

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