제출 #651674

#제출 시각아이디문제언어결과실행 시간메모리
651674rafatoa슈퍼트리 잇기 (IOI20_supertrees)C++17
11 / 100
183 ms24060 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #pragma GCC optimize ("Ofast") #define double ld const int inf = 2e9; const int INF = 4e18; #define F first #define S second #define vi vector<int> #define vvi vector<vi> #define pi pair<int, int> #define vpi vector<pi> #define vb vector<bool> #define vvb vector<vb> #define pb push_back #define read(a) for(auto &x:a) cin >> x; #define print(a) for(auto x:a) cout << x << " "; cout << "\n"; #define rs resize #define as assign #define vc vector<char> #define vvc vector<vc> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define ppb pop_back #define MP make_pair // #define int ll void build(vvi b); struct DSU{ int n; vi link, sz; void init(int x){ n = x; link.resize(n); sz.resize(n); for(int i=0; i<n; i++) link[i] = i, sz[i] = 1; } int find(int x){ if(x == link[x]) return x; return link[x] = find(link[x]); } bool same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ a = find(a), b = find(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); sz[a] += sz[b]; link[b] = a; } }; int construct(vvi p){ int n = p.size(); for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(p[i][j] == 3) return 0; vvi b(n, vi(n, 0)); DSU dsu; dsu.init(n); for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(p[i][j] > 0) dsu.unite(i, j); vvi comp(n); for(int i=0; i<n; i++) comp[dsu.find(i)].pb(i); for(int i=0; i<n; i++) for(int j=0; j<comp[i].size(); j++) for(int k=j+1; k<comp[i].size(); k++) if(p[j][k] == 0) return 0; for(int i=0; i<n; i++){ if(comp[i].empty()) continue; DSU dsu2; dsu2.init(n); for(int j=0; j<comp[i].size(); j++) for(int k=j+1; k<comp[i].size(); k++) if(p[j][k] == 1) dsu2.unite(j, k); for(int j=0; j<comp[i].size(); j++) for(int k=j+1; k<comp[i].size(); k++) if((dsu2.same(j, k) && p[j][k] == 2) || (!dsu2.same(j, k) && p[j][k] == 1)) return 0; vvi sect(n); vi lims; for(int j=0; j<comp[i].size(); j++) sect[dsu2.find(j)].pb(j); for(int j=0; j<n; j++){ if(sect[j].empty()) continue; for(int k=0; k<sect[j].size()-1; k++) b[sect[j][k]][sect[j][k+1]] = b[sect[j][k+1]][sect[j][k]] = 1; lims.pb(sect[j].back()); } for(int j=0; j<lims.size()-1; j++) b[lims[j]][lims[j+1]] = b[lims[j+1]][lims[j]] = 1; if(lims.size() > 1) b[lims.front()][lims.back()] = b[lims.back()][lims.front()] = 1; } build(b); return 1; }

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

supertrees.cpp:9:17: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
    9 | const int INF = 4e18;
      |                 ^~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=0; j<comp[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~~
supertrees.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int k=j+1; k<comp[i].size(); k++)
      |                        ~^~~~~~~~~~~~~~~
supertrees.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j=0; j<comp[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~~
supertrees.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int k=j+1; k<comp[i].size(); k++)
      |                        ~^~~~~~~~~~~~~~~
supertrees.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int j=0; j<comp[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~~
supertrees.cpp:93:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int k=j+1; k<comp[i].size(); k++)
      |                        ~^~~~~~~~~~~~~~~
supertrees.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int j=0; j<comp[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~~
supertrees.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for(int k=0; k<sect[j].size()-1; k++)
      |                          ~^~~~~~~~~~~~~~~~~
supertrees.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int j=0; j<lims.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...