oj.uz

답안 #300242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
300242 2020-09-17T02:33:50 Z daniel920712 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 1 ms 384 KB 
#include "supertrees.h"
#include <vector>
#include <stdio.h>
using namespace std;
vector < int > how[1005];
vector < int > how2[1005];
vector < int > cycle;
int Father[1005];
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
int construct(vector < vector< int > > p)
{
	int n=p.size(),i,j,k,m;
	vector< vector<int> > answer;
	vector< int > row;
	for(i=0;i<n;i++) row.push_back(0);
	for(i=0;i<n;i++)
    {
        answer.push_back(row);
        Father[i]=i;
    }
	for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(p[i][j]==0&&Find(i)==Find(j)) return 0;
            else if(p[i][j]) Father[Find(i)]=Find(j);
        }
    }
    for(i=0;i<n;i++) how[Find(i)].push_back(i);
    for(i=0;i<n;i++)
    {
        m=how[i].size();
        if(m<=1) continue;

        for(auto j:how[i]) Father[j]=j;
        for(j=0;j<m;j++)
        {
            for(k=0;k<m;k++)
            {
                if(Find(how[i][j])==Find(how[i][k])&&p[how[i][j]][how[i][k]]==2) return 0;
                else if(p[how[i][j]][how[i][k]]==1) Father[Find(how[i][j])]=Find(how[i][j]);
            }
        }
        for(auto j:how[i]) how2[Find(j)].push_back(j);
        cycle.clear();
        for(auto j:how[i])
        {
            m=how2[j].size();
            if(m==0) continue;
            for(j=1;j<m;j++)
            {
                answer[how2[i][j-1]][how2[i][j]]=1;
                answer[how2[i][j]][how2[i][j-1]]=1;
            }
            cycle.push_back(how2[i][0]);
        }
        m=cycle.size();
        if(m==1) continue;
        for(j=1;j<m;j++)
        {
            answer[how[i][j-1]][how[i][j]]=1;
            answer[how[i][j]][how[i][j-1]]=1;
        }
        answer[how[i][m-1]][how[i][0]]=1;
        answer[how[i][0]][how[i][m-1]]=1;

    }
	build(answer);
	return 1;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 288 KB Too many ways to get from 1 to 4, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -