Submission #305718

#	Time	Username	Problem	Language	Result	Execution time	Memory
305718		bruce_test	Connecting Supertrees (IOI20_supertrees)	C++14	Compilation error	0 ms	0 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7;
vector<vi> b; vi p, p2, adj[1010], adj2[1010], tmp;
//void build(vector<vi> t){
//    int n = t.size();
//    for(int i=0; i<n; i++, cout<<endl)
//        for(int j=0; j<n; j++)
//            cout << t[i][j] << " ";
//}
int fd(int d, vi& p){ return d==p[d]? p[d]: p[d]=fd(p[d], p); }
inline void join(int u, int v, vi& p){
    int fu = fd(u, p), fv = fd(v, p);
    if(fu == fv) return;
    p[fu] = fv;
}
int construct(vector<vi> a) {
    int n = a.size(); b.resize(n, vi(n, 0)); p.resize(n, 0); p2.resize(n, 0);
    for(int i=0; i<n; i++) p[i] = p2[i] = i;
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(a[i][j] == 3) return 0;
            if(a[i][j]) join(i, j, p);
        }
    }
    for(int i=0; i<n; i++){
        adj[fd(i, p)].pb(i);
        for(int j=0; j<i; j++){
            if(!a[i][j] && fd(i, p) == fd(j, p)) return 0;
        }
    }
    for(int i=0; i<n; i++){
        if(adj[i].empty()) continue;
        for(int x: adj[i])
            for(int y: adj[i])
                if(a[x][y] == 1) join(x, y, p2);
        for(int x: adj[i])
            adj2[fd(x, p2)].pb(x);
        for(int x: adj[i]){
            if(adj2[x].empty()) continue;
            for(int xx: adj2[x])
                for(int yy: adj2[x])
                    if(a[xx][yy] != 1) return 0;
            int st = adj2[x][0], ed = adj2[x].back();
            if(adj2[x].size() > 1){
                b[st][ed] = b[ed][st] = 1;
                for(int j=1; j<adj2[x].size(); j++){
                    int u = adj2[x][j-1], v = adj2[x][j];
                    b[u][v] = b[v][u] = 1;
                }
            }
            tmp.pb(st);
        }
        if(tmp.size() == 2) return 0;
        if(tmp.size() > 1){
            int st = tmp[0], ed = tmp.back(); b[st][ed] = b[ed][st] = 1;
            for(int j=1; j<tmp.size(); j++){
                int u = tmp[j-1], v = tmp[j];
                b[u][v] = b[v][u] = 1;
            }
        }
        tmp.clear();
    }
    build(b);
    return 1;
}
//int main(){
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    //vector<vi> a = {{1,1,2,2}, {1,1,2,2}, {2,2,1,2}, {2,2,2,1}};
//    vector<vi> a = {{1, 3}, {3, 1}};
//    cout << construct(a) << endl;
//}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 for(int j=1; j<adj2[x].size(); j++){
      |                              ~^~~~~~~~~~~~~~~
supertrees.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(int j=1; j<tmp.size(); j++){
      |                          ~^~~~~~~~~~~
supertrees.cpp:78:5: error: 'build' was not declared in this scope
   78 |     build(b);
      |     ^~~~~