Submission #833746

#	Time	Username	Problem	Language	Result	Execution time	Memory
833746		andrey27_sm	슈퍼트리 잇기 (IOI20_supertrees)	C++17	56 / 100	165 ms	32076 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
mt19937 rnd(time(0));
vector<int> same_tree[1000];
vector<int> same_component[1000];
vector<int> cyc[1000];
int p[1000];
int pr(int v){
    if(p[v] == v) return v;
    return p[v] = pr(p[v]);
}
void un(int v,int u){
    v = pr(v);
    u = pr(u);
    if(v == u) return;
    if(rnd()&1) swap(u,v);
    p[u] = v;
}
bool used[1000];
int construct(vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(p[i][j] == 3) return 0;
            if(p[i][j] >= 1) same_component[i].push_back(j);
            if(p[i][j] == 1) same_tree[i].push_back(j);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        ::p[i] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(p[i][j]) un(i,j);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(p[i][j] == 0 and pr(i) == pr(j)) return 0;
        }
    }


    /*for (int i = 0; i < n; ++i)
    {
        ::p[i] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(p[i][j] == 1) un(i,j);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(p[i][j] != 1 and pr(i) == pr(j)) return 0;
        }
    }*/
    vector<vector<int>> graph(n,vector<int>(n));
    for (int i = 0; i < n; ++i)
    {
        sort(same_tree[i].begin(),same_tree[i].end());
        if(used[i]) continue;
        used[i] = 1;
        for(auto e:same_tree[i]){
            if(e == i) continue;
            used[e] = 1;
            graph[i][e] = 1;
            graph[e][i] = 1;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        used[i] = 0;
    }
    for (int i = 0; i < n; ++i)
    {
        if(used[i]) continue;
        used[i] = 1;
        set<int> C;
        for(auto e:same_component[i]){
            used[e] = 1;
            C.insert(same_tree[e][0]);
        }
        for(auto e:C) cyc[i].push_back(e);
        if(C.size() > 1) cyc[i].push_back(cyc[i][0]);
        for (int j = 0; j+1 < cyc[i].size(); ++j)
        {
            graph[cyc[i][j]][cyc[i][j+1]] = 1;
            graph[cyc[i][j+1]][cyc[i][j]] = 1;
        }
    }
    build(graph);
    return 1;
}

Compilation message (stderr)

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

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