제출 #301871

#제출 시각아이디문제언어결과실행 시간메모리
301871SOIVIEONE슈퍼트리 잇기 (IOI20_supertrees)C++14
0 / 100
5 ms5608 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; int ota[222222], bobo[222222]; int find(int x) { return (ota[x] == x ? x : ota[x] = find(ota[x])); } void unite(int x, int y) { x = find(x); y = find(y); ota[y] = x; } int find2(int x) { return (bobo[x] == x ? x : bobo[x] = find2(bobo[x])); } vector<int> v[222222]; void unite2(int x, int y) { x = find2(x); y = find2(y); bobo[y] = x; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> a; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); a.push_back(row); } for(int i = 0; i < n; i ++) ota[i] = i; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j ++) { if(p[i][j] == 1) { unite(i, j); } } } for(int i = 0; i < n; i ++) bobo[i] = ota[i]; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { int foo = find(i), hoo = find(j); if(p[i][j] == 2) { unite2(foo, hoo); } } } for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) { if(p[i][j] == 3) return 0; int boboi = find2(i), boboj = find2(j); int otai = find(i), otaj = find(j); if(otai == otaj) { if(p[i][j] != 1) return 0; } if(otai != otaj) { if(boboi == boboj) { if(p[i][j] != 2) return 0; } else{ if(p[i][j] != 0) return 0; } } //if(boboi != boboj && p[i][j] != 2) // return 0; if(otai == otaj) { if(otai != i) a[i][otai] = a[otai][i] = 1; } } vector<int> dead(n + 1, 0); set<int> s; for(int i = 0; i < n; i ++) { int o = find(i); if(dead[o]) continue; dead[o] = 1; v[bobo[o]].push_back(o); } for(int i = 0; i <= n; i ++) { vector<int> it = v[i]; if(it.size()==2) return 0; if(it.empty()) continue; //for(auto id : it) //cerr << id << ' '; //cerr << '\n'; for(int j = 1; j < it.size(); j ++) { a[it[j]][it[j-1]] = a[it[j-1]][it[j]] = 1; } a[it.back()][it[0]] = a[it[0]][it.back()]=1; } build(a); return 1; } /* 5 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 */

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:119:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j = 1; j < it.size(); j ++)
      |                        ~~^~~~~~~~~~~
#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...