글 읽기 - 데이터 확인 부탁드립니다.

jason9319 6년 전 0

자꾸 틀려서 dfs를 두번 이상 돌릴 경우 tle가 나도록 소스를 작성하였더니 제가 틀리던 53% 즈음에서 tle가 납니다..

트리구조가 아닌 입력이 주어지는 것 같습니다. ㅠㅠ

hyo123bin 6년 전 1

왜죠.. 왤까요.. 분명 다검사했는데 다시 검사하니까 트리가아닌게 있는걸까요 ㅠㅠ

진짜 제가 너무 죄송해요

대회전에 검수만 세번 했는데 정말 ㅠㅠ 어쩌다 이런일이.. 죄송해요.

아마 포레스트가 있는 것 같아요..

아마 재채점하면 맞으실거에요 소스는 가려주시길 부탁드ㅕ려요 ㅠㅠ

알려주셔서 감사합니다

jason9319 6년 전 0

ㅜㅜ 확인해주셔서 감사합니다

hyo123bin 6년 전 0

어..근데 다시확인해봤는데.. 왜 런타임에러가 안날까요

트리맞는것같은데 뭐지

#include<bits/stdc++.h>
using std::vector;
struct disjoint_set{
        vector<int> tree;
        disjoint_set(int n){
                tree.resize(n+1,-1);
        }
        int find(int a){
                if(tree[a]==-1)return a;
                return tree[a]=find(tree[a]);
        }
        void Union(int a,int b){
                int A=find(a);
                int B=find(b);
                assert(A!=B);
                tree[B]=A;
        }
};


int main(){
        int n;
        scanf("%d",&n);
        disjoint_set set(n+10);
        for(int i=0;i<n-1;i++){
                int a,b;
                assert(scanf("%d%d",&a,&b)!=EOF);
                set.Union(a,b);
        }
}

cokcjswo 6년 전 0

확인해보니 11시간 전에 재채점이 들어갔네요. 근데 지금도 테케가 이상한 느낌이지.... 흑

dfs돌렸는데 모두 방문했는지 assert넣었더니 런타임에러 뜨네요 ㅜㅜ

코드를 잘못 짠건가

#include <bits/stdc++.h>
// #pragma optimize("-O2")
#define pb push_back
#define fi first
#define se second
#define SIZE 10000
#define PAD 250
#define MOD 1000000000LL
#define MAXV 100111
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<vector<long long> > mat;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

int n, chk[1000111], inDeg[1000111], tc, ntc;
vector<int> adj[1000111];

void dfs(int node, int p, int cnt) {
	chk[node] = cnt;
	for(int next : adj[node])
		if(next != p)
			dfs(next, node, cnt+1);
}

int main () {
	scanf("%d",&n);
	// there isn't not terminal node
	// 1 !!! on n == 1 answer is 1!!!
	// assert(n != 1);
	if(n == 1)	printf("1\n"),exit(0);
	if(n == 2)	printf("0\n"),exit(0);
	for(int i=0;i<n-1;i++) {
		int a,b;	scanf("%d%d",&a,&b);
		adj[a].pb(b);	adj[b].pb(a);	
		inDeg[a]++, inDeg[b]++;
	}
	int root;
	for(int i=1;i<=n;i++) {
		if(inDeg[i] == 1)	tc++;
		else			ntc++, root = i;
	}
	// only one not terminal node
	if(ntc == 1) printf("%d\n",n-2), exit(0);

	dfs(root, 0, 1);
	for(int i=1;i<=n;i++)	assert(chk[i] != 0);

	// now there is no reason to choose terminal node as a root
	//cause terminal node can be plus factor but non terminal is not
	//and one step going anywhere from this node is gonna reverse odd and even, so we only need to check a or b
	int a = 0, b = 0;
	for(int i=1;i<=n;i++) {
		if(inDeg[i] == 1) {
			if(chk[i] % 2)		a++;
			else			b++;
		}
	}
	// printf("a %d b %d\n",a,b);
	printf("%d\n",max(a,b));
}

cokcjswo 6년 전 0

포레스트를 처리하니 맞는데

다시 생각해도 궁금하네요 n - 1개 간선으로 포레스트(적어도 컴퍼넌트가 2개 이상인)가 중복간선 없이 어떻게 나오징

중복간선이 있는건감

일단 포레스트(컴퍼넌트 2개 이상) 데이터 지워주세요 !!

cokcjswo 6년 전 0

아 문제 찾았다

정점 범위가 1<=a<=n이 아닌 정점이 들어있는 데이터가 있네요

그러니까 간선이 n-1개라도 포레스트가 만들어지는구나. (정점이 n개 초과인 셈이라)

hyo123bin 6년 전 1

ㅠㅜㅜ 데이터는1 번부터 n번까지 잘들어와요..

근데 제출만하면 이상하게 런타임에러네요 곧 고쳐질것같아요

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

문제

문제

출처

ICPC

데이터 확인 부탁드립니다.

jason9319 6년 전 0

hyo123bin 6년 전 1

jason9319 6년 전 0

hyo123bin 6년 전 0

cokcjswo 6년 전 0

cokcjswo 6년 전 0

cokcjswo 6년 전 0

hyo123bin 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말