Submission #1051444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051444		LittleOrange	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	126 ms	22220 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
	ll n;
	vector<ll> p;
	dsu(ll N):n(N),p(N,-1){}
	ll g(ll i){
		return p[i]<0?i:p[i]=g(p[i]);
	}
	bool e(ll a, ll b){
		return g(a)==g(b);
	}
	bool m(ll a, ll b){
		a = g(a);
		b = g(b);
		if(a==b) return false;
		if (p[a]>p[b]) swap(a,b);
		p[a] += p[b];
		p[b] = a;
		return true;
	}
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<ll>> ans(n,vector<ll>(n,0));
	dsu d(n);
	for(ll i = 0;i<n;i++) for(ll j = 0;j<n;j++){
		if (p[i][j]==3) return 0;
		if (p[i][j]) d.m(i,j);
	}
	for(ll i = 0;i<n;i++) for(ll j = 0;j<n;j++){
		if (!p[i][j]&&d.e(i,j)) return 0;
	}
	vector<ll> g;
	for(ll i = 0;i<n;i++) if(d.g(i)==i) g.push_back(i);
	ll gc = g.size();
	vector<vector<ll>> gs(gc);
	for(ll i = 0;i<n;i++) gs[lower_bound(g.begin(),g.end(),d.g(i))-g.begin()].push_back(i);
	for(auto &o : gs) if(o.size()>1){
		ll ty = 3;
		ll is_1 = 1, is_2 = 1;
		for(ll i : o) for(ll j : o) if(i!=j){
			if (p[i][j]!=1) is_1=0;
			if (p[i][j]!=2) is_2=0;
		}
		if(is_1) ty=1;
		if(is_2) ty=2;
		//cerr << "type=" << ty << endl;
		if (ty!=3){
			for(ll i = 1;i<o.size();i++) ans[o[i-1]][o[i]] = ans[o[i]][o[i-1]] = 1;
			if (ty == 2){
				if (o.size()==2) return 0;
				ans[o.front()][o.back()] = ans[o.back()][o.front()] = 1;
			}
		}else{
			ll m = o.size();
			dsu d(m);
			for(ll i = 0;i<m;i++)for(ll j = 0;j<m;j++) if(i!=j){
				if (p[o[i]][o[j]]==1) {
					//cerr << "gp " << i << " " << j << endl;
					d.m(i,j);
				}
			}
			for(ll i = 0;i<m;i++)for(ll j = 0;j<m;j++) if(i!=j){
				if (d.e(i,j)&&p[o[i]][o[j]]!=1) return 0;
			}
			vector<ll> c;
			for(ll i = 0;i<m;i++) if(d.g(i)==i) c.push_back(i);
			ll cc = c.size();
			//cerr << "cc=" << cc << endl;
			if (cc<3) return 0;
			vector<vector<ll>> cs(cc);
			for(ll i = 0;i<m;i++) cs[lower_bound(c.begin(),c.end(),d.g(i))-c.begin()].push_back(o[i]);
			/*for(ll i = 0;i<cc;i++){
				cerr << "cg " << i << ":";
				for(ll j : cs[i]) cerr << " " << j;
				cerr << "\n";
			}*/
			for(auto &cl : cs){
				for(ll i = 1;i<cl.size();i++) ans[cl[i-1]][cl[i]] = ans[cl[i]][cl[i-1]] = 1;
			}
			for(ll i = 1;i<cc;i++) ans[cs[i-1][0]][cs[i][0]] = ans[cs[i][0]][cs[i-1][0]] = 1;
			ans[cs.front()[0]][cs.back()[0]] = ans[cs.back()[0]][cs.front()[0]] = 1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:54:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(ll i = 1;i<o.size();i++) ans[o[i-1]][o[i]] = ans[o[i]][o[i-1]] = 1;
      |                 ~^~~~~~~~~
supertrees.cpp:84:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(ll i = 1;i<cl.size();i++) ans[cl[i-1]][cl[i]] = ans[cl[i]][cl[i-1]] = 1;
      |                  ~^~~~~~~~~~

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