제출 #401199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401199		my99n	슈퍼트리 잇기 (IOI20_supertrees)	C++14	0 / 100	1 ms	204 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int p[2000], mark[2020];
int find (int u) { return u==p[u]? u:p[u]=find(p[u]); }
bool merge (int i, int j) {
  // cerr << "merge " << find(i) << ' ' << find(j) << endl;
  if (find(i) == find(j)) return false;
  p[find(i)] = find(j);
  return true;
}

void log (vector<vector<int>> s) {
  cerr << "log" << endl;
  for (auto x : s) {
    for (auto y : x) {
      cerr << y << ' ';
    } cerr << endl;
  }
  cerr << endl;
}

vector<int> c;
vector<vector<int>> r;
int n;
void relax(int i) {
  for (int j = i+1; j < n; j++) {
    if (r[i][j] == 2) c.push_back(j);
  }
  c.push_back(i);
  for (auto x : c) {
    for (auto y : c) {
      r[x][y] = r[y][x] = 0;
    }
  }
}

int construct(vector<vector<int>> req) {
  r = req;
  // cerr << "hi" << endl;
	n = req.size();
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

  iota(p, p+n+1, 0);

  bool flag = true;
  for  (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (r[i][j] == 2) {
        c.clear();
        relax(i);
        for (int x = 1; x < c.size(); x++) {
          merge(c[x-1], c[x]);
          answer[c[x-1]][c[x]] = answer[c[x]][c[x-1]] = 1;
        } 
        answer[c.back()][c[0]] = answer[c[0]][c.back()] = 1;
      }
    }
  }
  for  (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      // cerr << i << ' ' << j << ' ' << find(i) << ' ' << find(j) << endl;
      if (req[i][j] == 0 and find(i) == find(j)) flag = false;
    }
  }

  if (flag == false) return 0;
	build(answer);
	return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int x = 1; x < c.size(); x++) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4