| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1322281 | opeleklanos | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <vector>
#include "supertrees.h"
using namespace std;
vector<vector<int>> c;
vector<vector<int>> adj;
int n;
int construct(vector<vector<int>> c1){
c = c1;
n = c[0].size();
adj.assign(n, vector<int>(n, 0));
for(int i = 0; i<n; i++) c[i].push_back(i);
sort(c.begin(), c.end());
int prev = 0;
int same = 0;
// vector<int> s;
vector<int> cycleNodes;
cycleNodes.push_back(0);
for(int i = 1; i<n; i++){
if(!c[i][0] != !c[prev][0]){
if(cycleNodes.size() > 1)
adj[c[cycleNodes[0]][n]][c[cycleNodes[cycleNodes.size()-1]][n]] =
adj[c[cycleNodes[cycleNodes.size()-1]][n]][c[cycleNodes[0]][n]] = 1;
cycleNodes.clear();
prev = same = i;
cycleNodes.push_back(i);
continue;
}
adj[c[same][n]][c[i][n]] = adj[c[i][n]][c[same][n]] = 1;
int s = 1;
for(int j = 0; j<n; j++) if(c[i][j] != c[same][j]) s = 0;
if(!s){
cycleNodes.push_back(i);
same = i;
}
}
if(cycleNodes.size() > 1)
adj[c[cycleNodes[0]][n]][c[cycleNodes[cycleNodes.size()-1]][n]] =
adj[c[cycleNodes[cycleNodes.size()-1]][n]][c[cycleNodes[0]][n]] = 1;
build(adj);
return 1;
}
int main(void){
freopen("input.txt", "r", stdin);
int n; cin>>n;
vector<vector<int>> c1;
c1.assign(n, vector<int>(n, 0));
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++) cin>>c1[i][j];
}
construct(c1);
}
