제출 #619746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619746		Sergio_2357	Simurgh (IOI17_simurgh)	C++17	0 / 100	2 ms	212 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

struct DSU {
    vi v, sz;
    int cg;
    int find(int x)
    {
        if (v[x] == -1)
            return x;
        v[x] = find(v[x]);
        return v[x];
    }
    void join(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        cg--;
        if (sz[a] > sz[b])
            swap(a, b);
        v[a] = b;
        sz[b] += sz[a];
    }
    DSU(int n)
    {
        v = vi(n + 10, -1);
        sz = vi(n + 10, 1);
        cg = n;
    }
};

bool test(vi u, vi v)
{
    DSU dsu(u.size());
    for (int i = 0; i < u.size(); i++)
        dsu.join(u[i], v[i]);
    return dsu.cg == 1;
}

vi to_list(int b, int ma)
{
    vi r;
    for (int i = 0; i < ma; i++) {
        if (b & (1ll << i))
            r.push_back(i);
    }
    return r;
}

vi find_roads(int n, vi u, vi v)
{
    //cout << "YES" << endl;
    int cnt = 0;
    for (int b = 0; b < (1ll << (u.size())); b++) {
        vi tu, tv;
        vi lst = to_list(b, u.size());
        for (int x : lst) {
            tu.push_back(u[x]);
            tv.push_back(v[x]);
        }
        if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1)) {
            cnt++;
            if (cnt >= 30000)
                while (true) {
                    cnt++;
                }
            return lst;
        }
    }
    return to_list((1ll << (n - 1)) - 1, n);
}

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

simurgh.cpp: In function 'bool test(vi, vi)':
simurgh.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < u.size(); i++)
      |                     ~~^~~~~~~~~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:67:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |         if (tu.size() == n - 1 && test(tu, tv) && (count_common_roads(lst) == n - 1)) {
      |             ~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30