Submission #545459

#	Time	Username	Problem	Language	Result	Execution time	Memory
545459		Leo121	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	203 ms	28188 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
using namespace std;
const int lim = 1e3;
int graph[lim + 2][lim + 2];
bool visitado[lim + 2];
int componente[lim + 2];
vector<int> lineas[lim + 2];
int n, numcomp;
void dfs(int u){
    forn(v, 0, n - 1){
        if(v != u && graph[u][v] && !componente[v]){
            componente[v] = componente[u];
            dfs(v);
        }
    }
}
int construct(vector<vector<int>> p) {
	n = p.size();
	forn(i, 0, n - 1){
        forn(j, 0, n - 1){
            graph[i][j] = p[i][j];
            if(graph[i][j] == 3){
                return 0;
            }
        }
	}
	forn(i, 0, n - 1){
        if(!componente[i]){
            componente[i] = ++ numcomp;
            dfs(i);
        }
	}
	forn(i, 0, n - 1){
        forn(j, i + 1, n - 1){
            if(!graph[i][j] && componente[i] == componente[j]){
                return 0;
            }
        }
	}
	vector<int> aux[lim + 2];
	forn(i, 0, n - 1){
        if(!visitado[i]){
            lineas[componente[i]].push_back(i);
            visitado[i] = 1;
            forn(j, 0, n - 1){
                if(graph[i][j] == 1){
                    aux[i].push_back(j);
                }
            }
            for(int &u : aux[i]){
                visitado[u] = 1;
                forn(j, 0, n - 1){
                    if(graph[u][j] == 1 && graph[i][j] != 1){
                        return 0;
                    }
                }
            }
        }
	}
	forn(i, 1, numcomp){
        if((int) lineas[i].size() == 2){
            return 0;
        }
	}
	vector<vector<int>> res;
	res.resize(n);
	forn(i, 0, n - 1){
        res[i].resize(n);
        forn(j, 0, n - 1){
            res[i][j] = 0;
        }
	}
	int tamanio;
	forn(i, 1, numcomp){
	    tamanio = lineas[i].size();
        forn(j, 1, tamanio - 1){
            res[lineas[i][j - 1]][lineas[i][j]] = 1;
            res[lineas[i][j]][lineas[i][j - 1]] = 1;
        }
        if(tamanio > 1){
            res[lineas[i][0]][lineas[i][tamanio - 1]] = 1;
            res[lineas[i][tamanio - 1]][lineas[i][0]] = 1;
        }
        for(int &u : lineas[i]){
            tamanio = aux[u].size();
            forn(j, 1, tamanio - 1){
                res[aux[u][j]][aux[u][j - 1]] = 1;
                res[aux[u][j - 1]][aux[u][j]] = 1;
            }
        }
	}
	build(res);
	return 1;
}

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