oj.uz

답안 #519826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519826 2022-01-27T11:28:07 Z A_D 슈퍼트리 잇기 (IOI20_supertrees) C++14
11 / 100
 196 ms 26172 KB 
#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;
const int N=1e3+110;
vector<int> g1[N];
vector<int> g2[N];
bool vis[N];
vector<vector<int>> answer;
vector<int> vec;
void dfs1(int u)
{
    vis[u]=1;
    for(auto x:g1[u]){
        if(vis[x])continue;
        answer[u][x]=1;
        answer[x][u]=1;
        dfs1(x);
    }
}

int construct(vector<vector<int>> p){
	int n = p.size();
	vector<int> tmp(n);
	for(int i=0;i<n;i++){
        answer.push_back(tmp);
	}

	for(int i=0;i<n;i++){
        g1[i].push_back(i);
        g2[i].push_back(i);
        for(int j=i;j<n;j++){
            int v=p[i][j];
            if(v==3||(i==j&&v!=1)||p[i][j]!=p[j][i]){
                return 0;
            }
            if(v==2){
                g2[i].push_back(j);
                g2[j].push_back(i);

            }
            if(v==1&&i!=j){
                g1[i].push_back(j);
                g1[j].push_back(i);
            }
        }
	}
	for(int i=0;i<n;i++){
        sort(g1[i].begin(),g1[i].end());
        sort(g2[i].begin(),g2[i].end());
	}
	for(int i=0;i<n;i++){
        if(vis[i]==0){
            dfs1(i);
            int sz=g1[i].size();
            for(int j=0;j<sz-1;j++){
              //  if(g1[g1[i][j]]!=g1[g1[i][j+1]])return 0;
            }
        }
	}
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++){
        if(vis[i]==0){
            int sz=g2[i].size();
            for(int j=0;j<sz-1;j++){
                vis[g2[i][j]]=1;vis[g2[i][j+1]]=1;
                answer[g2[i][j]][g2[i][j+1]]=1;
                answer[g2[i][j+1]][g2[i][j]]=1;
               // if(g2[g2[i][j]]!=g2[g2[i][j+1]])return 0;
            }
            answer[g2[i][0]][g2[i][sz-1]]=1;
            answer[g2[i][sz-1]][g2[i][0]]=1;
        }
	}
    /*
	for(int i=0;i<n;i++){
        cout<<i<<" : ";
        for(auto y:g1[i]){
            cout<<y<<" ";
        }
        cout<<endl;
    }

    for(int i=0;i<n;i++){
        cout<<i<<" : ";
        for(auto y:g2[i]){
            cout<<y<<" ";
        }
        cout<<endl;
    }
    */


    for(int i=0;i<n;i++){
        answer[i][i]=0;
    }
	build(answer);
	return 1;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 179 ms 26172 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 179 ms 26172 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 7 ms 1140 KB Output is correct
13 Correct 168 ms 22076 KB Output is correct
14 Incorrect 0 ms 332 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 42 ms 5828 KB Output is correct
5 Correct 180 ms 22564 KB Output is correct
6 Correct 166 ms 22156 KB Output is correct
7 Correct 190 ms 24128 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 42 ms 5812 KB Output is correct
10 Correct 174 ms 22552 KB Output is correct
11 Correct 196 ms 22076 KB Output is correct
12 Correct 185 ms 25152 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 1 ms 332 KB Too many ways to get from 0 to 4, should be 1 found no less than 2
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 179 ms 26172 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 7 ms 1140 KB Output is correct
13 Correct 168 ms 22076 KB Output is correct
14 Incorrect 0 ms 332 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 8 ms 1400 KB Output is correct
7 Correct 179 ms 26172 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 7 ms 1140 KB Output is correct
13 Correct 168 ms 22076 KB Output is correct
14 Incorrect 0 ms 332 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -