제출 #934126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934126		raul2008487	슈퍼트리 잇기 (IOI20_supertrees)	C++17	19 / 100	179 ms	24312 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
struct DSU{
    vl par;
    vector<vector<ll>> e;
    void init(ll n){
        e.resize(n + 1);
        par.resize(n + 1);
        ll i;
        for(i = 0; i < n; i++){
            e[i].pb(i);
            par[i] = i;
        }
    }
    ll get(ll x){
        if(par[x] == x){
            return x;
        }
        return par[x] = get(par[x]);
    }
    bool connected(ll x, ll y){
        return (get(x) == get(y));
    }
    bool unite(ll a, ll b){
        a = get(a);
        b = get(b);
        if(a == b){return false;}
        if(e[a].size() < e[b].size()){
            swap(a, b);
        }
        par[b] = a;
        for(auto x: e[b]){
            e[a].pb(x);
            par[x] = a;
        }
        e[b].clear();
        return true;
    }
};
int construct(vector<vector<int>> p) {
	DSU dsu1, dsu2;
    ll n = p.size(), i, j;
    dsu1.init(n);
    dsu2.init(n);
    vector<vector<ll>> ans(n, vector<ll> (n, 0));
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 1){
                dsu1.unite(i, j);
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] != 1 && dsu1.connected(i, j)){
                //cout << "1" << endl;
                return 0;
            }
        }
    }
//    for(i = 0; i < n; i++){cout << dsu1.get(i) << ' ';}cout << endl;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i][j] == 2){
                if(dsu2.unite(dsu1.get(i), dsu1.get(j))){
//                    cout << dsu1.get(i) <<  ' ' << dsu1.get(j) << endl;
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(i == j){continue;}
            if(p[i][j] != 2 && dsu2.connected(i, j)){
                //cout << "2" << endl;
                return 0;
            }
        }
    }
    vector<bool> used(n, 0), vis(n, 0);
    for(i = 0; i < n; i++){
        ll x = dsu2.get(i);
        if(dsu2.e[x].size() == 2){/*cout << "3" << endl;*/return 0;}
        if(dsu2.e[x].size() > 2 && !used[x]){
            for(j = 0;j < dsu2.e[x].size() - 1; j++){
                ans[dsu2.e[x][j]][dsu2.e[x][j + 1]] = 1;
                ans[dsu2.e[x][j + 1]][dsu2.e[x][j]] = 1;
            }
            ans[dsu2.e[x][0]][dsu2.e[x].back()] = ans[dsu2.e[x].back()][dsu2.e[x][0]] = 1;
            used[x] = 1;
        }
        x = dsu1.get(i);
        if(dsu1.e[x].size() < 2){continue;}
        if(!vis[x]){
            for(j = 0;j < dsu1.e[x].size() - 1; j++){
                ans[dsu1.e[x][j]][dsu1.e[x][j + 1]] = 1;
                ans[dsu1.e[x][j + 1]][dsu1.e[x][j]] = 1;
            }
            ans[dsu1.e[x][0]][dsu1.e[x].back()] = ans[dsu1.e[x].back()][dsu1.e[x][0]] = 1;
            vis[x] = 1;
        }
    }

    build(ans);
    return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1

*/

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:94:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(j = 0;j < dsu2.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(j = 0;j < dsu1.e[x].size() - 1; j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~

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