Submission #651673

#TimeUsernameProblemLanguageResultExecution timeMemory
651673rafatoa슈퍼트리 잇기 (IOI20_supertrees)C++17
Compilation error
0 ms0 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; }

Compilation message (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 'll construct(std::vector<std::vector<long long int> >)':
supertrees.cpp:80:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int j=0; j<lims.size()-1; j++)
      |                      ~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccyNFbMk.o: in function `construct(std::vector<std::vector<long long, std::allocator<long long> >, std::allocator<std::vector<long long, std::allocator<long long> > > >)':
supertrees.cpp:(.text+0xd39): undefined reference to `build(std::vector<std::vector<long long, std::allocator<long long> >, std::allocator<std::vector<long long, std::allocator<long long> > > >)'
/usr/bin/ld: /tmp/ccX1MFxk.o: in function `main':
grader.cpp:(.text.startup+0x39a): undefined reference to `construct(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status