Submission #862273

#	Time	Username	Problem	Language	Result	Execution time	Memory
862273		Liudas	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	183 ms	24148 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
void dfs(int head, vector<vector<int>> &arr, vector<int> &vis, vector<vector<int>> &path, int N, vector<int> &col, int c){
    vis[head] = true;
    col[head] = c;
    for(int i = 0; i < N; i ++){
        if(!vis[i] && arr[head][i] == 1){
            path[i][head] = 1;
            path[head][i] = 1;
            dfs(i, arr, vis, path, N, col, c);
        }
    }
}
void dfs2(int head, vector<vector<int>> &path, int N, int &e, vector<int> &vis, vector<vector<int>> &arr, vector<int> &col){
    vis[head] = true;
    for(int i = 0; i < N; i ++){
        if(col[i] == col[head]){
            vis[i] = true;
        }
    }
    e = head;
    for(int i = 0; i < N; i ++){
        if(!vis[i] && arr[head][i] == 2){
            int c = col[i];
            for(int j = 0; j < N; j ++){
                if(col[j] == c){
                    col[j] = col[head];
                }
            }
            path[i][head] = 1;
            path[head][i] = 1;
            dfs2(i, path, N, e, vis, arr, col);
        }
    }
}
int construct(vector<vector<int>> arr){
    int N = arr.size();
    vector<int> vis(N, 0), col(N, -1);
    bool pos = true;
    vector<vector<int>> path(N, vector<int>(N));
    int c = 1;
    for(int i = 0; i < N; i ++){
        if(!vis[i]){
            dfs(i, arr, vis, path, N, col, c++);
        }
    }
    fill(vis.begin(), vis.end(), 0);
    for(int i = 0; i < N; i ++){
        if(!vis[i] && *max_element(arr[i].begin(), arr[i].end()) == 2){
            int t = -1;
            dfs2(i, path, N, t, vis, arr, col);
            if(path[i][t]){
                pos = false;
            }
            path[i][t] = 1;
            path[t][i] = 1;
        }
    }
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            if(arr[i][j] == 0 && col[i] == col[j]){
                pos = false;
            }
            if(arr[i][j] == 3){
                pos = false;
            }
        }
    }
    if(pos)
    build(path);
    return pos;
}

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