Submission #172023

#	Time	Username	Problem	Language	Result	Execution time	Memory
172023		Milki	Izlet (COI19_izlet)	C++14	100 / 100	904 ms	101464 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);

  //freopen("case.txt", "r", stdin);
	//freopen("provjera", "w", stdout);

  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){
  if(f(x) == f(y)) return;
  E[x].push_back(y); E[y].push_back(x);
  par[f(y)] = f(x);
}

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);
     // cout << i _ j;
      for(int k = 0; k < (int)two[j].size(); ++k)
        if(dist[i][ two[j][k] ] == 2){
          spoji(i, two[j][k]);
        //  cout << " " << two[j][k];
        }
     // cout << " dvakomp\n";
    }
}

bool bio[MAXN], sranje[MAXN];
int seen[MAXN];

void 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])
      seen[color[e]] ++;

    if(dist[origin][x] != dist[origin][e])
      sranje[color[e]] = true;
    dfs(e, origin, x);
  }
}

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

  while(!Q.empty()){
    int x = Q.front(); Q.pop();
    //TRACE(x);
    for(int i = 0; i < n; ++i)
      seen[i] = 0;
    for(int i = 0; i < cnt; ++i)
      sranje[i] = false;

    bio[x] = true;
    dfs(x, x);
    for(int i = 1; i < cnt; ++i){
      //TRACE(sranje[i]); TRACE(seen[i]);
      if(!sranje[i] && seen[i] > 0){
        color[x] = i;
        break;
      }
    }

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

    for(auto e : E[x]){
      if(bio[e]) continue;
      bio[e] = true;
      Q.push(e);
    }
  }
  //cout << cnt << "\n";
}

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

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

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

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