제출 #386226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386226		loctildore	Izlet (COI19_izlet)	C++14	18 / 100	640 ms	54348 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
int n;
int mat[3069][3069],colour[3069];
int parent[3069],parentcopy[3069];
int weight[3069];
vector<pair<int,int>> edges;
int find(int x){
  if (x==parent[x]) {
    return x;
  }
  parent[x]=find(parent[x]);
  return parent[x];
}
void merge(int x,int y) {
  x=find(x);
  y=find(y);
  if (x==y) {
    return;
  }
  if (weight[x]<weight[y]) {
    swap(x,y);
  }
  weight[x]+=weight[y];
  parent[y]=x;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n;
  cin>>n;
  for (int i = 0; i < n; i++) {
    parent[i]=i;
    weight[i]=1;
    colour[i]=i;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin>>mat[i][j];
      if (mat[i][j]==1) {
        merge(i,j);
      }
    }
  }
  for (int i = 0; i < 3069; i++) {
    parentcopy[i]=find(i);
  }
  for (int i = 0; i < n; i++) {
    if (i!=parentcopy[i]) {
      continue;
    }
    for (int j = i; j < n; j++) {
      if (j!=parentcopy[j]) {
        continue;
      }
      if (mat[i][j]==2) {
        if (find(i)!=find(j)) {
          edges.push_back({i,j});
          merge(i,j);
        }
        else {
          colour[j]=colour[i];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout<<colour[parentcopy[i]]+1<<' ';
  }
  cout<<endl;
  for (int i = 0; i < n; i++) {
    if (i!=parentcopy[i]) {
      cout<<parentcopy[i]+1<<' '<<i+1<<endl;
    }
  }
  for (auto i : edges) {
    cout<<i.f+1<<' '<<i.s+1<<endl;
  }
  return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57