Submission #735054

#	Time	Username	Problem	Language	Result	Execution time	Memory
735054		vjudge1	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	356 ms	22116 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define MAX 300001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
struct dsu{
    vector<ll> e;
    void init(int n){
        e.resize(n+1,-1);
    }
    int get(int x){
        if(e[x]<0){
            return x;
        }
        else{
            return e[x]=get(e[x]);
        }
    }
    int size(int x){
        return -e[get(x)];
    }
    bool same_set(int x,int y){
        return (get(x)==get(y));
    }
    bool unite(int x,int y){
        x=get(x);
        y=get(y);
        if(x==y){
            return false;
        }
        if(e[x]>e[y]){
            swap(x,y);
        }
        e[x]+=e[y];
        e[y]=x;
        return true;
    }
};
int construct(vector<vector<int>> p) {
	int n = p.size();
	dsu d;
	d.init(n);
	vector<vector<int>> answer;
	answer.resize(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(p[i][j]==1){
                d.unite(i,j);
            }
            if(p[i][j]==3){
                return 0;
            }
        }
	}
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(d.same_set(i,j) && p[i][j]!=1){
                //cout << 1 << "\n";
                return 0;
            }
        }
	}
	dsu d2;
	dsu d3;
	d2.init(n);
	d3.init(n);
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(p[i][j]==2){
                d2.unite(d.get(i),d.get(j));
            }
            else if(p[i][j]==3){
                d3.unite(d.get(i),d.get(j));
            }
        }
	}
	for(int i=0;i<n;i++){
        if(d2.size(i)==2){
            //cout << 2 << "\n";
            return 0;
        }
	}
	for(int i=0;i<n;i++){
	    if(d3.size(i)==2 || d3.size(i)==3){
            //cout << 3 << "\n";
            return 0;
	    }
	}
	for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	        if(p[i][j]==0 && (d2.same_set(i,j) || d3.same_set(i,j))){
	            return 0;
	        }
            if(d2.same_set(i,j) && d3.same_set(i,j) && i!=j){
                //cout << 4 << "\n";
                return 0;
            }
	    }
	}
	set<ll> st;
	for(int i=0;i<n;i++){
        st.ins(i);
	}
	for(int i=0;i<n;i++){
	    if(st.find(i)==st.end()){
            continue;
	    }
	    vector<int> c;
	    for(auto x:st){
            if(d.same_set(i,x)){
                c.pb(x);
            }
	    }
	    for(int i=1;i<c.size();i++){
	        answer[c[i-1]][c[i]]=1;
	        answer[c[i]][c[i-1]]=1;
	    }
	    for(auto x:c){
            st.erase(x);
	    }
	}
	st.clear();
	for(int i=0;i<n;i++){
        st.ins(i);
	}
	for(int i=0;i<n;i++){
	    if(st.find(i)==st.end()){
            continue;
	    }
	    set<int> e;
	    vector<int> c;
	    for(auto x:st){
            if(d2.same_set(i,x)){
                e.ins(d.get(x));
            }
	    }
	    for(auto x:e){
            c.pb(x);
	    }
	    if(c.size()>1){
	        for(int i=1;i<c.size();i++){
                answer[c[i-1]][c[i]]=1;
                answer[c[i]][c[i-1]]=1;
            }
            answer[c[0]][c[c.size()-1]]=1;
            answer[c[c.size()-1]][c[0]]=1;
	    }
	    for(auto x:c){
            st.erase(x);
	    }
	}
	st.clear();
	for(int i=0;i<n;i++){
        st.ins(i);
	}
	for(int i=0;i<n;i++){
	    if(st.find(i)==st.end()){
            continue;
	    }
	    set<int> e;
	    vector<int> c;
	    for(auto x:st){
            if(d3.same_set(i,x)){
                e.ins(d.get(x));
            }
	    }
	    for(auto x:e){
            c.pb(x);
	    }
	    if(c.size()>1){
	        for(int i=1;i<c.size();i++){
                answer[c[i-1]][c[i]]=1;
                answer[c[i]][c[i-1]]=1;
            }
            answer[c[0]][c[c.size()-1]]=1;
            answer[c[c.size()-1]][c[0]]=1;
            answer[c[1]][c[c.size()-1]]=1;
            answer[c[c.size()-1]][c[1]]=1;
	    }
	    for(auto x:c){
            st.erase(x);
	    }
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:161:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |      for(int i=1;i<c.size();i++){
      |                  ~^~~~~~~~~
supertrees.cpp:188:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |          for(int i=1;i<c.size();i++){
      |                      ~^~~~~~~~~
supertrees.cpp:218:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |          for(int i=1;i<c.size();i++){
      |                      ~^~~~~~~~~

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