oj.uz

답안 #172013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172013 2019-12-30T20:12:00 Z Milki Izlet (COI19_izlet) C++14
18 / 100
 811 ms 92164 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", "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];

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";

  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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 782 ms 90316 KB Output is correct
3 Correct 811 ms 90464 KB Output is correct
4 Correct 771 ms 92164 KB Output is correct
5 Correct 766 ms 89652 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 602 ms 42872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 782 ms 90316 KB Output is correct
3 Correct 811 ms 90464 KB Output is correct
4 Correct 771 ms 92164 KB Output is correct
5 Correct 766 ms 89652 KB Output is correct
6 Incorrect 602 ms 42872 KB Output isn't correct
7 Halted 0 ms 0 KB -