Submission #582099

#	Time	Username	Problem	Language	Result	Execution time	Memory
582099		MohamedFaresNebili	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	252 ms	22108 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#include <ext/pb_ds/assoc_container.hpp>
 
        using namespace std;
        using namespace __gnu_pbds;
 
        using ll = long long;
        using pi = pair<ll, pair<ll, ll>>;
        using ii = pair<int, int>;
 
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
 
        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;
 
        int N, par[1001]; vector<int> S[1001];
        int findSet(int v) {
            if(par[v] == v) return v;
            return par[v] = findSet(par[v]);
        }
        void unionSet(int u, int v) {
            u = findSet(u), v = findSet(v);
            if(S[u].size() < S[v].size()) swap(u, v);
            for(auto e : S[v]) S[u].pb(e);
            par[v] = u; S[v].clear();
        }
 
        int construct(vector<vector<int>> P) {
            N = P.size();
          	vector<vector<int>> B(N, vector<int>(N, 0));
            for(int l = 0; l < N; l++)
                par[l] = l, S[l].pb(l);
            for(int l = 0; l < N; l++) {
                for(int i = l + 1; i < N; i++) {
                    if(findSet(l) == findSet(i) || P[l][i] == 0)
                        continue;
                    unionSet(l, i);
                }
            }
            for(int l = 0; l < N; l++) {
                for(int i = l + 1; i < N; i++) {
                    if(P[l][i] == 0 && findSet(l) == findSet(i))
                        return 0;
                    if(P[l][i] == 1 && findSet(l) != findSet(i))
                        return 0;
                }
            }
            for(int l = 0; l < N; l++) {
                for(int i = 1; i < S[l].size(); i++)
                    B[S[l][i]][S[l][i - 1]] = B[S[l][i - 1]][S[l][i]] = 1;
                int U = S[l][0], V = S[l][S[l].size() - 1];
                if(P[U][V] <= 1) continue;
                B[U][V] = B[V][U] = 1;
            }
            build(B);
            return 1;
        }

Compilation message (stderr)

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

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