oj.uz

Submission #225788

# Submission time Handle Problem Language Result Execution time Memory
225788 2020-04-21T15:36:28 Z quocnguyen1012 Izlet (COI19_izlet) C++14
100 / 100
 754 ms 74616 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 692 ms 53752 KB Output is correct
3 Correct 675 ms 53820 KB Output is correct
4 Correct 665 ms 53552 KB Output is correct
5 Correct 680 ms 53496 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 53752 KB Output is correct
2 Correct 707 ms 53816 KB Output is correct
3 Correct 754 ms 73848 KB Output is correct
4 Correct 723 ms 74616 KB Output is correct
5 Correct 613 ms 53752 KB Output is correct
6 Correct 618 ms 60536 KB Output is correct
7 Correct 517 ms 49448 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 692 ms 53752 KB Output is correct
3 Correct 675 ms 53820 KB Output is correct
4 Correct 665 ms 53552 KB Output is correct
5 Correct 680 ms 53496 KB Output is correct
6 Correct 594 ms 53752 KB Output is correct
7 Correct 707 ms 53816 KB Output is correct
8 Correct 754 ms 73848 KB Output is correct
9 Correct 723 ms 74616 KB Output is correct
10 Correct 613 ms 53752 KB Output is correct
11 Correct 618 ms 60536 KB Output is correct
12 Correct 517 ms 49448 KB Output is correct
13 Correct 677 ms 54516 KB Output is correct
14 Correct 682 ms 61432 KB Output is correct
15 Correct 679 ms 53808 KB Output is correct
16 Correct 720 ms 57976 KB Output is correct
17 Correct 711 ms 60124 KB Output is correct
18 Correct 664 ms 53584 KB Output is correct
19 Correct 628 ms 53732 KB Output is correct
20 Correct 658 ms 53624 KB Output is correct
21 Correct 679 ms 54252 KB Output is correct
22 Correct 653 ms 53868 KB Output is correct
23 Correct 689 ms 54392 KB Output is correct
24 Correct 681 ms 60648 KB Output is correct
25 Correct 663 ms 53752 KB Output is correct