oj.uz

Submission #172023

# Submission time Handle Problem Language Result Execution time Memory
172023 2019-12-30T20:40:32 Z Milki Izlet (COI19_izlet) C++14
100 / 100
 904 ms 101464 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 885 ms 87624 KB Output is correct
3 Correct 842 ms 87636 KB Output is correct
4 Correct 904 ms 89648 KB Output is correct
5 Correct 846 ms 86984 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 40400 KB Output is correct
2 Correct 896 ms 101464 KB Output is correct
3 Correct 867 ms 74084 KB Output is correct
4 Correct 877 ms 74852 KB Output is correct
5 Correct 682 ms 57764 KB Output is correct
6 Correct 749 ms 61212 KB Output is correct
7 Correct 542 ms 50424 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 885 ms 87624 KB Output is correct
3 Correct 842 ms 87636 KB Output is correct
4 Correct 904 ms 89648 KB Output is correct
5 Correct 846 ms 86984 KB Output is correct
6 Correct 702 ms 40400 KB Output is correct
7 Correct 896 ms 101464 KB Output is correct
8 Correct 867 ms 74084 KB Output is correct
9 Correct 877 ms 74852 KB Output is correct
10 Correct 682 ms 57764 KB Output is correct
11 Correct 749 ms 61212 KB Output is correct
12 Correct 542 ms 50424 KB Output is correct
13 Correct 799 ms 54744 KB Output is correct
14 Correct 818 ms 61688 KB Output is correct
15 Correct 731 ms 59940 KB Output is correct
16 Correct 811 ms 61700 KB Output is correct
17 Correct 796 ms 61116 KB Output is correct
18 Correct 721 ms 54500 KB Output is correct
19 Correct 786 ms 68100 KB Output is correct
20 Correct 742 ms 63228 KB Output is correct
21 Correct 801 ms 65328 KB Output is correct
22 Correct 734 ms 54868 KB Output is correct
23 Correct 776 ms 55160 KB Output is correct
24 Correct 831 ms 61244 KB Output is correct
25 Correct 742 ms 56824 KB Output is correct