Submission #543423

#	Time	Username	Problem	Language	Result	Execution time	Memory
543423		Ronin13	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	190 ms	24116 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    int lead[n];
    for(int i = 0; i < n; i++){
        lead[i] = i;
    }
    for(int i = 0; i < n; i++){
        if(p[i][i] != 1)return 0;
        for(int j = 0; j < n; j++){
            if(p[i][j] != p[j][i]) return 0;
            if(p[j][i] == 3)return 0;
        }
    }
    vector< vector <int> > ch(n + 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if( p[i][j]  ){
                if(lead[i] != lead[j] && (lead[i] < i || lead[j] != j) )return 0;
                lead[i] = lead[j];
            }
            if((!p[i][j]) && lead[i] == lead[j])return 0;
        }
        ch[lead[i]].pb(i);
    }
    vector< vector<int> > cmp;
    for(int i = 0; i < n; i++){
        if(!ch[i].empty())cmp.pb(ch[i]);
    }
    for(int i = 0; i < n; i++){
        lead[i] = i;
    }
    vector < vector <int> > ans;
    ans.resize(n);
    for(int i = 0; i < n; i++){
        ans[i].resize(n);
    }
    vector<vector<int> > cur1;
    cur1.resize(n);
    for(vector<int> &cur : cmp){
        for(int to: cur){
            for(int i = 0; i < to; i++){
                if(p[to][i] == 1){
                    if(lead[to] != lead[i] && (lead[to] < to || lead[i] != i) )return 0;
                    else lead[to] = lead[i];
                }
                if(p[to][i] == 2){
                    if(lead[to] == lead[i])return 0;
                }
            }
            cur1[lead[to]].pb(to);
        }
        vector<int>vv;
        for(int to : cur){
           // cout << to << ' ';
            if(cur1[to].size() == 0)continue;
            for(int i = 0; i < cur1[to].size() - 1; i++){
                //if(i == 0)vv.pb(cur1[to][i]);
               // cout << cur1[to][i] << ' ';
                int x = cur1[to][i];
                int y = cur1[to][i + 1];
                ans[x][y] = ans[y][x] = 1;
            }
            vv.pb(cur1[to][0]);
        }
        if(vv.size() == 2)return 0;
        if(vv.size() <= 1)continue;
        for(int i = 0; i < vv.size() - 1; i++){
            int x = vv[i];
            int y = vv[i + 1];
           // cout << x << ' ' << y << "\n";
            ans[x][y] = ans[y][x] = 1;
        }
        int x = vv.back();
       // cout << x;
        int y = vv[0];
        ans[x][y] = ans[y][x] = 1;
    }
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }*/
    build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:67:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int i = 0; i < cur1[to].size() - 1; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i = 0; i < vv.size() - 1; 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