Submission #1245373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245373		qwusha	슈퍼트리 잇기 (IOI20_supertrees)	C++20	Compilation error	0 ms	0 KiB

supertrees

#include "supertrees.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

int inf = 1e9 + 7;


struct dsu {
    vector<int> par;
    vector<int> sz;
    void init(int n) {
        par.assign(n, 0);
        sz.assign(n, 1);
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }
    int get_par(int v) {
        if (par[v] == v) {
            return v;
        }
        int ans = get_par(par[v]);
        par[v] = ans;
        return ans;
    }
    void unitik(int v, int u) {
        v = get_par(v);
        u = get_par(u);
        if (sz[v] < sz[u]) {
            swap(v, u);
        }
        sz[v] += sz[u];
        par[u] = v;
    }
};


int construct(vector<vector<int>> p) {
    int n = p.size();
    dsu dsubig;
    dsubig.init(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] > 0 && dsubig.get_par(i) != dsubig.get_par(j)) {
                dsubig.unitik(i, j);
            }
        }
    }
    bool ok = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 0 && dsubig.get_par(i) == dsubig.get_par(j)) {
                ok = 0;
            }
        }
    }
    if (!ok) {
        return 0;
    }
    vector<vector<int>> b(n, vector<int>(n));
    vector<vector<int>> gr(n);
    for (int i = 0; i < n; i++) {
        gr[dsubig.get_par(i)].push_back(i);
    }

    dsu grdsu;
    map<int, vector<int>> mp;
    for (int j = 0; j < n; j++) {
        if (gr[j].size() < 2)
            continue;
        grdsu.init(gr[j].size());
        mp.clear();
        for (int i = 0; i < gr[j].size(); i++) {
            for (int q = i + 1; q < gr[j].size(); q++) {
                if (p[gr[j][i]][gr[j][q]] == 1 && grdsu.get_par(i) != grdsu.get_par(q)) {
                    grdsu.unitik(i, q);
                }
            }
        }
        bool ch = 1;
        for (int i = 0; i < gr[j].size(); i++) {
            for (int q = i + 1; q < gr[j].size(); q++) {
                if (p[gr[j][i]][gr[j][q]] >= 2 && grdsu.get_par(i) == grdsu.get_par(q)) {
                    ch = 0;
                }
            }
        }
        if (!ch)
            return 0;
        for (int i = 0; i < gr[j].size(); i++) {
            mp[grdsu.get_par(i)].push_back(i);
        }
        vector<int> bosses;
        for (auto [boss, ve] : mp) {
            bosses.push_back(boss);
            for (int i = 0; i < ve.size() - 1; i++) {
                b[gr[j][ve[i]]][gr[j][ve[i + 1]]] = 1;
                b[gr[j][ve[i + 1]]][gr[j][ve[i]]] = 1;
            }
        }
        if (bosses.size() == 1) {
            continue;
        }
        if (bosses.size() == 2) {
            return 0;
        }
        for (int i = 0; i < bosses.size(); i++) {
            b[gr[j][bosses[i]]][gr[j][bosses[(i + 1) % bosses.size()]]] = 1;
            b[gr[j][bosses[(i + 1) % bosses.size()]]][gr[j][bosses[i]]] = 1;
        }
        vector<vector<int>> grogra(gr[j].size(), vector<int>(gr[j].size(), -1));
        set<pair<int, int>> sus;
        for (int i = 0; i < gr[j].size(); i++) {
            for (int q = 0; q < gr[j].size(); q++) {
                int bi = grdsu.get_par(i), bj = dsubig.get_par(q);
                if (grogra[bi][bj] != -1 && grogra[bi][bj] != p[gr[j][i]][gr[j][q]]) {
                    return 0;
                }
                grogra[bi][bj] = p[gr[j][i]][gr[j][q]];
                if (p[gr[j][i]][gr[j][q]] == 3) {
                    sus.insert({min(bi, bj), max(bi,bj)});
                }
            }
        }
        if (sus.size() > 1) {
            return 0;
        }
        if (sus.size() == 0) {
            continue;
        }
        if (bosses.size() == 3) {
            return 0;
        }
        b[gr[j][bosses[sus[0].fi]]][gr[j][bosses[sus[0].se]]] = 1;
        b[gr[j][bosses[sus[0].se]]][gr[j][bosses[sus[0].fi]]] = 1;
    }


    build(b);
    return 1;

}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:141:27: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and 'int')
  141 |         b[gr[j][bosses[sus[0].fi]]][gr[j][bosses[sus[0].se]]] = 1;
      |                           ^
supertrees.cpp:141:53: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and 'int')
  141 |         b[gr[j][bosses[sus[0].fi]]][gr[j][bosses[sus[0].se]]] = 1;
      |                                                     ^
supertrees.cpp:142:27: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and 'int')
  142 |         b[gr[j][bosses[sus[0].se]]][gr[j][bosses[sus[0].fi]]] = 1;
      |                           ^
supertrees.cpp:142:53: error: no match for 'operator[]' (operand types are 'std::set<std::pair<int, int> >' and 'int')
  142 |         b[gr[j][bosses[sus[0].se]]][gr[j][bosses[sus[0].fi]]] = 1;
      |                                                     ^