Submission #1069303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069303		hasan2006	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	168 ms	24176 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2e5 + 9 , mod = 1e9 + 7;
ll a[N] ,  b[N] , dp[N];

//int press(string a){}
int construct(vector<vector<int>> v){
    ll i , j , l , r , s  = 0, f , n , m , x , y , k;
    n = v.size();

    vector<vector<int>>c(n);
    for(i = 0; i < n; i++)
        c[i].resize(n);
    for(i = 0; i < n; i++){
        if(b[i] != 0)
            continue;
        vector<pair<int,pair<int,int>>>vc;
        vector<int>v1 , v2 , v3;
        for(j = 0; j < n; j++)
            if(v[i][j])
                b[j] = 1 , v1.pb(j);
        l = r = 0;
        for(x = 0; x < v1.size(); x++)
            for(y = x + 1; y < v1.size(); y++){
                vc.pb({v[v1[x]][v1[y]] , {v1[x] , v1[y]}});
                if(v[v1[x]][v1[y]] == 2)
                    l = 1;
                if(v[v1[x]][v1[y]] == 3)
                    r = 1;
            }
        sort(all(vc));
        if(v1.size() == 1)
            continue;
        if((l == 1 && r == 1) || vc.front().fi == 0){
            return 0;
        }
        for(auto to : vc)
            if(to.fi == 1 && to.se.fi != to.se.se)
                b[to.se.fi] = b[to.se.se] = 2;
        set<int>st;
        for(auto to : v1){
            st.insert(to);
            if(b[to] == 1)
                v2.pb(to);
            else
                v3.pb(to);
        }
        f = -1;
        for(auto to : v3){
            if(f != -1)
                c[to][f] = c[f][to] = 1;
            f = to;
        }

        if(v2.size()){
            if(v3.size())
                v2.pb(v3.back());
            if(v2.size() <= vc.back().fi){
                return 0;
            }
            f = v2.back();
            for(auto to : v2)
                c[f][to] = c[to][f] = 1 , f = to;
            if(vc.back().fi == 3)
                c[v2[0]][v2[2]] = c[v2[2]][v2[0]] = 1;
        }
        for(auto to : v1){
            ll L = 0 ,R = 0 , s =0;
            for(j = 0; j < n ; j++)
                if(v[to][j] != 0){
                    if(st.find(j) == st.end())
                        return 0;
                    s++;
                    if(to == j)
                        continue;
                    if(v[to][j] == 2)
                        L = 1;
                    else if(v[to][j] == 3)
                        R = 1;
                    else {
                        if(b[to] == 1 || b[j] == 1)
                            return 0;
                    }
                }
            if((L > l) || (R > r) || s != v1.size())
                return 0;
        }
    }
/*    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++)
            cout<<c[i][j]<<" ";
        cout<<"\n";
    }*/
    build(c);
    return 1;
}

/*
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}*/
// Author : حسن

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(x = 0; x < v1.size(); x++)
      |                    ~~^~~~~~~~~~~
supertrees.cpp:43:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(y = x + 1; y < v1.size(); y++){
      |                            ~~^~~~~~~~~~~
supertrees.cpp:77:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |             if(v2.size() <= vc.back().fi){
      |                          ^
supertrees.cpp:104:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             if((L > l) || (R > r) || s != v1.size())
      |                                      ~~^~~~~~~~~~~~
supertrees.cpp:27:24: warning: unused variable 's' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                        ^
supertrees.cpp:27:40: warning: unused variable 'm' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                        ^
supertrees.cpp:27:52: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll i , j , l , r , s  = 0, f , n , m , x , y , k;
      |                                                    ^

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