oj.uz

Submission #386226

# Submission time Handle Problem Language Result Execution time Memory
386226 2021-04-06T07:05:27 Z loctildore Izlet (COI19_izlet) C++14
18 / 100
 640 ms 54348 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 621 ms 54196 KB Output is correct
3 Correct 622 ms 54232 KB Output is correct
4 Correct 599 ms 53996 KB Output is correct
5 Correct 640 ms 54208 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 627 ms 54348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 621 ms 54196 KB Output is correct
3 Correct 622 ms 54232 KB Output is correct
4 Correct 599 ms 53996 KB Output is correct
5 Correct 640 ms 54208 KB Output is correct
6 Incorrect 627 ms 54348 KB Output isn't correct
7 Halted 0 ms 0 KB -