글 읽기 - 어디가 틀린걸까요..? 60프로 넘으면 틀린다고 나옵니다..

dorinee_restart 2년 전 0

주석 달아놨구요, 어느 반례때문에 60프로 넘어서 걸리는지 잘 모르겠습니다.. ㅜ 알려주시면 감사하겠습니다..

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int n;
int last;
int realans;
int l[200001];
int r[200001];
int cnt = 0;
void inorder(int x) { // 중위순회를 할때 마지막에 나오는 숫자 찾기위해 만든 함수
	if (l[x] != 0) {
		 inorder(l[x]);
	}
    if (x == -1)return;
	last = x; // last가 마지막 숫자
	if (r[x] != 0) {
		inorder(r[x]);
	}
}
void Yusa(int x) {// 유사 중위순회 함수
	if (l[x] != 0) { 
		cnt++; Yusa(l[x]);
	}
	if (r[x] != 0) {
		cnt++; Yusa(r[x]);
	}
	if (x == -1)return;
	cnt++; // 다 cnt++를 시킨후 마지막에 값을 빼야함.
}
void Height(int x, int ccnt) { // 트리의 높이 구하기 위해 만든 함수
	if (l[x] != 0 or r[x] != 0) {
		ccnt++;
		Height(l[x], ccnt);
		Height(r[x], ccnt);
	}
	if (x == last) { // 중위순회를 할때 마지막 값과 x가 같을때, 트리의 높이
		realans = ccnt; return;
	}
}
int main() {
    fastio;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (b != -1) l[a] = b;
		if (c != -1) r[a] = c;
	}
	Yusa(1);
	inorder(1);
	Height(1, 0);
	bool check = true;
	if (r[1] != 0) check = false; 
	if (check == true) cout << cnt - 1 << endl; // 루트노드의 오른쪽 자식이 없으면 
    // 다시 루트노드로 되돌아와야하는것까지 계산해야하니깐 cnt-1
	if( check == false)	cout << cnt -realans - 1 << endl; // 아닐때는 cnt-1에서 트리의 높이를 빼줌
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀린걸까요..? 60프로 넘으면 틀린다고 나옵니다..

dorinee_restart 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말