Submission #800217

#	Time	Username	Problem	Language	Result	Execution time	Memory
800217		TimDee	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	207 ms	22140 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

struct DSU {
    vector<int> p,sz;
    DSU(int n) {
        forn(i,n) p.pb(i), sz.pb(1);
    }
    int get(int u) {
        return p[u]==u?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u), v=get(v);
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }
};

int construct(vector<vector<int>> p) {
    int n=p.size();
    DSU dsu(n);
    forn(i,n) forn(j,n) if (p[i][j]) dsu.uni(i,j);
    vector<vector<int>> v(n);
    forn(i,n) v[dsu.get(i)].pb(i);

    vector<vector<int>> ans(n,vector<int>(n,0));

    forn(i,n) {
        if (!v[i].size()) continue;
        if (v[i].size()==1) continue;
        DSU dsu2(n);
        for(auto&x:v[i]) {
            for(auto&y:v[i]) {
                if (p[x][y]==1) dsu2.uni(x,y);
                if (p[x][y]==0) return 0;
            }
        }
        for(auto&x:v[i]) {
            for(auto&y:v[i]) {
                if (dsu2.get(x)==dsu2.get(y)) {
                    if (p[x][y]!=1) return 0;
                }
            }
        }
        vector<vector<int>> u(n);
        for(auto&x:v[i]) u[dsu2.get(x)].pb(x);

        forn(j,n) {
            if (!u[j].size()) continue;
            if (u[j].size()==1) continue;
            forn(k,u[j].size()-1) ans[u[j][k]][u[j][k+1]]=ans[u[j][k+1]][u[j][k]]=1;
        }

        vector<int> two;
        for(auto&x:v[i]) {
            if (x!=u[dsu2.get(x)].back()) continue;
            int z=3;
            for(auto&y:v[i]) {
                if (dsu2.get(x)==dsu2.get(y)) continue;
                if (p[x][y]!=2) return 0;
                z&=p[x][y]==2;
            }
            if (z==1) two.pb(x);
        }
        if (two.size()>0 && two.size()<3) return 0;
        forn(j,two.size()) {
            ans[two[j]][two[(j+1)%two.size()]]=ans[two[(j+1)%two.size()]][two[j]]=1;
        }
    }

    build(ans);

    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   61 |             forn(k,u[j].size()-1) ans[u[j][k]][u[j][k+1]]=ans[u[j][k+1]][u[j][k]]=1;
      |                  ~~~~~~~~~~~~~~~
supertrees.cpp:61:13: note: in expansion of macro 'forn'
   61 |             forn(k,u[j].size()-1) ans[u[j][k]][u[j][k+1]]=ans[u[j][k+1]][u[j][k]]=1;
      |             ^~~~
supertrees.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
......
   76 |         forn(j,two.size()) {
      |              ~~~~~~~~~~~~       
supertrees.cpp:76:9: note: in expansion of macro 'forn'
   76 |         forn(j,two.size()) {
      |         ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4