Submission #302859

#	Time	Username	Problem	Language	Result	Execution time	Memory
302859		whaleee	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	593 ms	69112 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

struct trip {
    int ones=0,twos=0,threes=0;
};

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n);
	forn(i,n) {
		vi empty(n,0);
		answer[i]= empty;
	}
	
    map<int, set<int>>node_to_friends;
	vector<set<int>> clusters;
	vector<trip> class_type(n,{0,0,0});
	vi cluster_vec(n,-1);
	int cnt = 0;
	forn(i, n) {
		int cnt0 = 0;
		int cnt1 = 0;
		int cnt2 = 0;
		int cnt3 = 0;

		if (cluster_vec[i] == -1) {
			cluster_vec[i] = cnt;
			cnt++;
		}
		int cluster_id = cluster_vec[i];

		forn(j,n) {
			if (p[i][j] == 0) {
				cnt0++;
			}
			else if (p[i][j] == 1) {
				cnt1++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
			}
			else if (p[i][j] == 2) {
				cnt2++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
			}
			else if (p[i][j] == 3) {
				cnt3++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
				
			}
            else {assert(0);}
		}

		if (cnt1 == 1 && cnt0 == n-1) {
			continue;
		}
		else {
            // check that there is connection
            forn(j,i) {
                if (cluster_vec[j] == cluster_id  && p[i][j] == 0) {
                    return 0;
                }
            if (p[i][j] == 1) {class_type[i].ones++; class_type[j].ones++;node_to_friends[i].insert(j);node_to_friends[j].insert(i);}
            if (p[i][j] == 2) {class_type[i].twos++; class_type[j].twos++;}
            if (p[i][j] == 3) {class_type[i].threes++; class_type[j].threes++;}
            }
        }
	}

	forn(i,cnt) {
		map<pair<int, pair<int,int>>, set<int>> combo_to_cnt;
        int cnt = 0;
		forn(j, n) {
			if (cluster_vec[j] == i) {
				// combo_to_cnt[{class_type[j].ones, {class_type[j].twos,class_type[j].threes}}]++;
                combo_to_cnt[{class_type[j].ones, {class_type[j].twos,class_type[j].threes}}].insert(j);
                cnt++;
			}   
		}
        if (cnt  <= 1) {
            continue;
        }
        vi circle;
        int to_push_start = -1;
        int to_push_end = -1;
        int two_pure = -1;
        int three_pure = -1;
        for(const auto &myPair : combo_to_cnt) {
            if (myPair.fi.fi == 0 && myPair.fi.se.fi == 0 && myPair.fi.se.se >0 ) {
                three_pure = myPair.se.size();
            }
            if (myPair.fi.fi == 0 && myPair.fi.se.fi > 0) {
                two_pure = myPair.se.size();
                int cnt = 0;
                int cur_node = -1;
                for (int node: myPair.se) {
                    if (cnt == 0) {
                        // circle.pb(node);
                        to_push_start = node;
                    }
                    else {
                        answer[node][cur_node] = 1;
                        answer[cur_node][node] = 1;
                    }
                    
                    cur_node = node;
                    cnt++;
                    if (cnt == myPair.se.size()) {
                        // circle.pb(node);
                        to_push_end = node;
                    }
                }
                continue;
            }
            
            
            int cnt = 0;
            int cur_node = -1;
            bool cont = false;
            vector<bool> visited(n, 0);
            for (int node: myPair.se) {
                if (visited[node]) {continue;}
                visited[node] = true;
                circle.pb(node);
                cur_node = node;
                for (int next_node: node_to_friends[node]) {
                    if (visited[next_node]) {return 0;}
                    visited[next_node] = true;
                    answer[next_node][cur_node] = 1;
                    answer[cur_node][next_node] = 1;
                    cur_node = next_node;
                }
            }
        }
        if (to_push_end != -1) {
            circle.insert(circle.begin(), to_push_start);
            circle.pb(to_push_end);
        }
        
        if ((two_pure == 1 || two_pure == 2) && circle.size() <= 2) {
            return 0;
        }
        if ((three_pure == 0 || three_pure == 1 || three_pure == 2 || three_pure == 3 || three_pure == 4)) {
            return 0;
        }
        if (three_pure == circle.size()) {
            return 0;
        }
        int bonus;
        if (two_pure == - 1) {
            bonus = 1;
        }
        else {
            bonus = 0;
        }
        forn(j, circle.size()-1 + bonus) {
            if (circle[j] != circle[(j+1)%circle.size()]) {
                answer[circle[j]][circle[(j+1)%circle.size()]] = 1;
                answer[circle[(j+1)%circle.size()]][circle[j]] = 1;
            }
        }
    }


	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:134:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |                     if (cnt == myPair.se.size()) {
      |                         ~~~~^~~~~~~~~~~~~~~~~~~
supertrees.cpp:143:17: warning: unused variable 'cnt' [-Wunused-variable]
  143 |             int cnt = 0;
      |                 ^~~
supertrees.cpp:145:18: warning: unused variable 'cont' [-Wunused-variable]
  145 |             bool cont = false;
      |                  ^~~~
supertrees.cpp:172:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         if (three_pure == circle.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