제출 #976077

#제출 시각아이디문제언어결과실행 시간메모리
976077efedmrlr슈퍼트리 잇기 (IOI20_supertrees)C++17
40 / 100
178 ms22352 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,popcnt") #include <bits/stdc++.h> #include "supertrees.h" #define lli long long int #define ld long double #define REP(i, n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end(); #define rall(x) x.rbegin(), x.rend() #define pb push_back #define MP make_pair using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 1e5 + 5; const int INF = 1e9 + 500; const int MOD = 1e9 + 7; struct DSU { vector<int> p, sz; int n; void make_set(int x) { p[x] = x; sz[x] = 1; } void init(int nn) { n = nn; p.assign(n + 3, 0); sz.assign(n + 3, 0); for(int i = 0; i < n; i++) { make_set(i); } } int find_set(int x) { return (x == p[x]) ? x : p[x] = find_set(p[x]); } bool union_set(int x, int y) { x = find_set(x); y = find_set(y); if(x == y) return 0; if(sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; p[y] = x; return 1; } }; int construct(std::vector<std::vector<int>> p) { int n = (int)p.size(); vector<vector<int> > ans(n, vector<int>(n, 0)); DSU ds, ds2; ds.init(n); // check zero bool f = 1; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(p[i][j]) { ds.union_set(i, j); } } } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(!p[i][j] && ds.find_set(i) == ds.find_set(j)) { f = 0; } } } if(!f) return 0; cerr << "zort" << endl; ds.init(n); ds2.init(n); // connect 1 and 2 separately for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(p[i][j] == 1) { ds.union_set(i, j); } else if(p[i][j] == 2) { ds2.union_set(i, j); } } } vector<vector<int> > cmp(n, vector<int>()); for(int i = 0; i < n; i++) { cmp[ds.find_set(i)].pb(i); } for(int i = 0; i < n; i++) { for(int j = 0; j < (int)cmp[i].size() - 1; j++) { // assert(j + 1 <= (int)cmp[i].size() - 1); // assert(ans[cmp[i][j]].size() == 4); // assert(ans[cmp[i][j + 1]].size() == 4); ans[cmp[i][j]][cmp[i][j + 1]] = 1; ans[cmp[i][j + 1]][cmp[i][j]] = 1; } } cmp.assign(n, vector<int>()); for(int i = 0; i < n; i++) { cmp[ds2.find_set(i)].pb(i); } for(int i = 0; i < n; i++) { if(cmp[i].size() == 2) { f = 0; } if(cmp[i].size() < 2) continue; for(int j = 0; j < cmp[i].size() - 1; j++) { ans[cmp[i][j]][cmp[i][j + 1]] = 1; ans[cmp[i][j + 1]][cmp[i][j]] = 1; } ans[cmp[i][0]][cmp[i][cmp[i].size() - 1]] = 1; ans[cmp[i][cmp[i].size() - 1]][cmp[i][0]] = 1; } if(!f) return 0; build(ans); return 1; }

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

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