제출 #362028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362028		Sorting	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	303 ms	32236 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;

vector<vector<int>> p, answer;
vector<int> adj[N], ans_adj[N], comp;
bool vis[N], c_vis[N];
int cnt[N], n;

void c_dfs(int u, vector<int> &line){
    c_vis[u] = true;
    line.push_back(u);

    for(int to: comp)
        if(!c_vis[to] && p[u][to] == 1 && u != to)
            c_dfs(to, line);
}

void add_edge(int x, int y){
    answer[x][y] = true;
    answer[y][x] = true;
    ans_adj[x].push_back(y);
    ans_adj[y].push_back(x);
}

void solve_comp(){
    vector<vector<int>> lines;
    for(int i: comp)
        if(!c_vis[i]){
            lines.push_back({});
            c_dfs(i, lines.back());
        }

    for(auto &line: lines)
        for(int i = 0; i < (int)line.size() - 1; ++i)
            add_edge(line[i], line[i + 1]);

    for(int i = 0; i < (int)lines.size(); ++i)
        add_edge(lines[i][0], lines[(i + 1) % lines.size()][0]);
}

void dfs(int u){
    vis[u] = true;
    comp.push_back(u);

    for(int i = 0; i < n; ++i)
        if(i != u && p[i][u] && !vis[i])
            dfs(i);
}

void valid_dfs(int u){
    vis[u] = true;
    cnt[u]++;
    for(int to: ans_adj[u])
        if(!vis[to])
            valid_dfs(to);
    vis[u] = false;
}

bool valid(){
    for(int i = 0; i < n; ++i)
        answer[i][i] = 0;

    fill(vis, vis + n, 0);
    for(int i = 0; i < n; ++i){
        fill(cnt, cnt + n, 0);
        valid_dfs(i);
        for(int j = 0; j < n; ++j)
            if(p[i][j] != cnt[j])
                return false;
    }
    return true;
}

void clear(){
    fill(vis, vis + n, false);
    fill(c_vis, c_vis + n, false);
    for(int i = 0; i < n; ++i){
        adj[i].clear();
        ans_adj[i].clear();
        cnt[i] = 0;
    }
}

bool solve(){
    clear();

    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j){
            if(p[i][j]){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }

    for(int i = 0; i < n; ++i)
        if(!vis[i]){
            comp.clear();
            dfs(i);
            solve_comp();
        }

    return valid();
}

int construct(vector<vector<int>> _p) {
    p = _p;
	n = p.size();
    answer.clear();
	answer.resize(n, vector<int>(n, 0));

    if(solve()){
	   build(answer);
	   return 1;
    }
    return 0;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
/*
2
1 3
3 1
*/

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4