oj.uz

답안 #619746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619746 2022-08-02T15:31:17 Z Sergio_2357 Simurgh (IOI17_simurgh) C++17
0 / 100
 2 ms 212 KB 
#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);
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB correct
2 Incorrect 2 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -