제출 #306757

#제출 시각아이디문제언어결과실행 시간메모리
306757Ruxandra985슈퍼트리 잇기 (IOI20_supertrees)C++14
40 / 100
271 ms22264 KiB
#include <bits/stdc++.h> #include "supertrees.h" #define DIMN 1010 using namespace std; int tt[DIMN] , c[DIMN] , f[DIMN] , t[DIMN]; vector <int> x , cycle; int root (int x){ while (tt[x] > 0) x = tt[x]; return x; } int roott (int x){ while (t[x] > 0) x = t[x]; return x; } int construct(vector<vector<int>> p) { int n = p.size() , i , ri , rj , j , caz , r; vector<vector<int>> answer; for (i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } for (i = 0 ; i < n ; i++) tt[i] = -1; for (i = 0 ; i < n ; i++){ f[i] = 0; c[i] = 0; for (j = 0 ; j < n ; j++){ if (p[i][j] == 3) return 0; /// ce teapa monumentala if (p[i][j] && i != j){ c[i] = (c[i] | p[i][j]); /// i si j in aceeasi componenta conexa ri = root(i); rj = root(j); if (ri != rj){ if (tt[ri] < tt[rj]){ tt[ri] += tt[rj]; tt[rj] = ri; } else { tt[rj] += tt[ri]; tt[ri] = rj; } } } } } for (i = 0 ; i < n ; i++){ for (j = 0 ; j < n ; j++){ if (!p[i][j]){ /// i si j in aceeasi componenta conexa ri = root(i); rj = root(j); if (ri == rj) /// sunt in aceeasi cc si n ar trb sa fie return 0; } } } for (r = 0 ; r < n ; r++){ if (tt[r] < 0){ x.clear(); for (i = 0 ; i < n ; i++){ if (root(i) == r) x.push_back(i); } /// x = componenta conexa de acum caz = 0; for (i = 0 ; i < x.size() ; i++){ caz = (caz | c[x[i]]); } if (caz == 0) continue; else if (caz == 1){ /// lant if (x.size() < 2) return 0; for (i = 0 ; i < x.size() - 1 ; i++){ answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1; } } else if (caz == 2){ /// un ciclu simplu if (x.size() < 3) return 0; for (i = 0 ; i < x.size() - 1 ; i++){ answer[x[i]][x[i + 1]] = answer[x[i + 1]][x[i]] = 1; } answer[x[0]][x.back()] = answer[x.back()][x[0]] = 1; } else { /// cazul cand sunt si 1 si 2 for (i = 0 ; i < n ; i++) t[i] = -1; cycle.clear(); int ok = 0; for (i = 0 ; i < x.size() ; i++){ if (c[x[i]] == 2){ cycle.push_back(x[i]); f[x[i]] = 1; } else if (c[x[i]] == 1){ return 0; } } for (i = 0 ; i < x.size() ; i++){ for (j = 0 ; j < x.size() ; j++){ //if (r == 24) //printf ("a"); if (i != j && p[x[i]][x[j]] == 1){ ri = roott(x[i]); rj = roott(x[j]); if (ri != rj){ answer[ri][rj] = answer[ri][rj] = 1; if (t[ri] < t[rj]){ t[ri] += t[rj]; t[rj] = ri; } else { t[rj] += t[ri]; t[ri] = rj; } } } } } for (i = 0 ; i < x.size() ; i++){ if (c[x[i]] == 3){ ri = roott(x[i]); if (!f[ri]){ f[ri] = 1; cycle.push_back(ri); } } } if (cycle.size() < 3){ return 0; } for (i = 0 ; i < cycle.size() - 1 ; i++){ answer[cycle[i]][cycle[i + 1]] = answer[cycle[i + 1]][cycle[i]] = 1; } answer[cycle[0]][cycle.back()] = answer[cycle.back()][cycle[0]] = 1; } } } //printf ("%d\n\n",answer[0][228]); build(answer); return 1; }

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (i = 0 ; i < x.size() ; i++){
      |                          ~~^~~~~~~~~~
supertrees.cpp:118:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (i = 0 ; i < x.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~
supertrees.cpp:143:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:153:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:154:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |                     for (j = 0 ; j < x.size() ; j++){
      |                                  ~~^~~~~~~~~~
supertrees.cpp:185:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |                 for (i = 0 ; i < x.size() ; i++){
      |                              ~~^~~~~~~~~~
supertrees.cpp:203:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |                 for (i = 0 ; i < cycle.size() - 1 ; i++){
      |                              ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:142:21: warning: unused variable 'ok' [-Wunused-variable]
  142 |                 int ok = 0;
      |                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...