Submission #171998

#	Time	Username	Problem	Language	Result	Execution time	Memory
171998		Milki	Izlet (COI19_izlet)	C++14	18 / 100	766 ms	85700 KiB

izlet

#include<bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int MAXN = 3e3 + 5;

int subtask, n, dist[MAXN][MAXN], par[MAXN], color[MAXN];
vector <int> E[MAXN];

void load(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> subtask >> n;
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      cin >> dist[i][j];
}

int f(int x){
  if(par[x] == x) return x;
  return par[x] = f(par[x]);
}

void spoji(int x, int y){
  x = f(x); y = f(y);
  if(x == y) return;
  E[x].push_back(y); E[y].push_back(x);
  par[y] = x;
}

vector<vector<int>> comp;

void create_tree(){
  for(int i = 0; i < n; ++i)
    par[i] = i;

  vector <bool> done(n, false);
  vector <vector<int>> two(n);

  for(int i = 0; i < n; ++i){
    vector<int> tmp;
    for(int j = i + 1; j < n; ++j){
      if(dist[i][j] == 1 && f(i) != f(j)){
        spoji(i, j);
      }
      if(dist[i][j] == 2){
        two[i].push_back(j);
        two[j].push_back(i);
      }
    }
  }

  for(int i = 0; i < n; ++i)
    for(int j = i + 1; j < n; ++j){
      if(dist[i][j] != 2 || f(i) == f(j)) continue;

      spoji(i, j);

      for(int k = 0; k < (int)two[j].size(); ++k)
        if(dist[i][ two[j][k] ] == 2 && two[j][k] != i){
          spoji(i, two[j][k]);
        }
    }
}

bool bio[MAXN];

int dfs(int x, int origin, int p = -1){
  for(auto e : E[x]){
    if(!bio[e] || e == p) continue;

    if(dist[origin][x] == dist[origin][e] && color[x] != color[e])
      return color[e];
    int ret = dfs(e, origin, x);
    if(ret != 0)
      return ret;
  }
  return 0;
}

void color_tree(){
  int cnt = 1;
  queue<int> Q; Q.push(0);
  bio[0] = true;

  while(!Q.empty()){
    int x = Q.front(); Q.pop();

    color[x] = dfs(x, x);
    bio[x] = true;

    if(color[x] == 0)
      color[x] = cnt ++;

    for(auto e : E[x]){
      if(bio[e]) continue;
      bio[e] = true;
      Q.push(e);
    }
  }
}

void print_tree(){
  for(int i = 0; i < n; ++i)
    cout << color[i] << " ";
  cout << "\n";

  int cunt = 0;
  for(int i = 0; i < n; ++i)
    for(auto j : E[i])
      if(i < j)
        cout << i + 1 _ j + 1 << "\n", cunt ++;
  assert(cunt == n - 1);
}

int main(){
  load();
  create_tree();
  color_tree();
  print_tree();
}

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