Submission #304288

#	Time	Username	Problem	Language	Result	Execution time	Memory
304288		abacaba	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	285 ms	22344 KiB

supertrees

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
#include "supertrees.h"
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
 
// typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const ll INF = 2e18;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e3 + 15;
 
bitset <N> d[N];
 
int par[2][N];
 
int find(int v, int i) {
    if(v == par[i][v])
        return v;
    return par[i][v] = find(par[i][v], i);
}
 
void unio(int a, int b, int i) {
    a = find(a, i);
    b = find(b, i);
    if(a != b)
        par[i][b] = a;
}
 
bool used[N];
 
int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> row(n, vector <int> (n, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            d[i][j] = p[i][j] != 0;
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            if(d[i][k])
                d[i] |= d[k];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(d[i][j] ^ (p[i][j] != 0))
                return 0;
    for(int i = 0; i < n; ++i)
        par[0][i] = par[1][i] = i;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if(d[i][j])
                unio(i, j, 0);
    for(int i = 0; i < n; ++i) {
        if(used[i])
            continue;
        vector <int> cur = {};
        for(int j = 0; j < n; ++j)
            if(find(i, 0) == find(j, 0))
                cur.pb(j);
        vector <int> cycle = {};
        for(int j = 0; j < cur.size(); ++j) {
            int v = cur[j];
            if(used[v])
                continue;
            if(!cycle.empty())
                row[cycle.back()][v] = row[v][cycle.back()] = 1;
            cycle.pb(v);
            used[v] = true;
            for(int u : cur) {
                if(p[u][v] == 1 && !used[u]) {
                    used[u] = used[v] = true;
                    row[u][v] = row[v][u] = 1;
                    unio(v, u, 1);
                    v = u;
                }
            }
        }
        if(cycle.size() > 1)
            row[cycle[0]][cycle.back()] = row[cycle.back()][cycle[0]] = 1;
    }
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j) {
            if(p[i][j] == 0 && find(i, 0) != find(j, 0))
                continue;
            if(p[i][j] == 1 && find(i, 1) == find(j, 1))
                continue;
            if(p[i][j] == 2 && find(i, 0) == find(j, 0) && find(i, 1) != find(j, 1))
                continue;
            return 0;
        }
    build(row);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0; j < cur.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