Submission #225788

#	Time	Username	Problem	Language	Result	Execution time	Memory
225788		quocnguyen1012	Izlet (COI19_izlet)	C++14	100 / 100	754 ms	74616 KiB

izlet

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 3005, inf = 1e9;

int a[maxn][maxn];
vector<int> adj[maxn];
int N, col[maxn], lab[maxn];
bool vis[maxn];
int depth[maxn], cnt[maxn];
vector<ar<int, 2>> node;

int finds(int u)
{
  if(lab[u] < 0) return u;
  return lab[u] = finds(lab[u]);
}

void add(int x, int y)
{
  if(finds(x) == finds(y)) return;
  adj[x].eb(y); adj[y].eb(x);
  x = finds(x); y = finds(y);
  if(lab[y] < lab[x]) swap(x, y);
  lab[x] += lab[y]; lab[y] = x;
}

void dfs(int u, int p = -1)
{
  for(int v : adj[u]) if(v != p){
    depth[v] = depth[u] + 1;
    dfs(v, u);
  }
}

void trav(int u, int num, int r)
{
  vis[u] = true;
  if(u != r){
    if(col[u] == 0) return;
    cnt[col[u]]++;
    if(cnt[col[u]] == 1){
      ++num;
    }
    if(a[r][u] == num && col[r] == 0){
      col[r] = col[u];
    }
  }
  for(int v : adj[u]) if(!vis[v]){
    trav(v, num, r);
  }
  cnt[col[u]]--;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> N;
  for(int i = 1; i <= N; ++i){
    for(int j = 1; j <= N; ++j){
      cin >> a[i][j];
    }
  }
  fill(lab + 1, lab + 1 + N, -1);
  for(int i = 1; i <= N; ++i){
    for(int j = 1; j <= N; ++j){
      if(a[i][j] == 1)
        add(i, j);
    }
  }
  for(int i = 1; i <= N; ++i){
    for(int j = 1; j <= N; ++j){
      if(a[i][j] == 2)
        add(i, j);
    }
  }
  dfs(1);
  for(int i = 1; i <= N; ++i)
    node.pb({depth[i], i});
  sort(node.begin(), node.end());
  int co = 0;
  for(auto & all : node){
    memset(vis, 0, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    trav(all[1], 0, all[1]);
    if(col[all[1]] == 0)
      col[all[1]] = ++co;
  }
  for(int i = 1; i <= N; ++i)
    cout << col[i] << " \n"[i == N];
  for(int i = 1; i <= N; ++i){
    for(int j : adj[i]){
      if(i < j)
        cout << i << ' ' << j << '\n';
    }
  }
}

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