Submission #296981

#	Time	Username	Problem	Language	Result	Execution time	Memory
296981		Trickster	Simurgh (IOI17_simurgh)	C++14	13 / 100	3032 ms	512 KiB

simurgh

#include "simurgh.h"
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define N 100
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) int(a.size())
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int P[N];
int lm, m;
int vis[100010];
vector <int> arr, U, V;

int ata(int x)
{
    if(P[x] == x) return x;
    return P[x] = ata(P[x]);
}

void uni(int a, int b)
{
    a = ata(a);
    b = ata(b);

    if(a == b) return;

    P[a] = b;
}

void bit(int x)
{
    if(x == m) {
        for(int i = 0; i < lm; i++) P[i] = i;

        vector <int> trie;
        for(int i = 0; i < m; i++) {
            if(vis[i] == 0) continue;
            
            trie.pb(i);
            uni(U[i], V[i]);
        }
        set <int> S;
        for(int i = 0; i < lm; i++) S.insert(ata(i));
        
        if(S.size() == 1 && trie.size() == lm-1) {
            int x = count_common_roads(trie);

            if(x == lm-1) {
                arr.clear();
                for(auto i: trie) arr.pb(i);
            }
        }

        return;
    }

    for(int i = 0; i < 2; i++) {
        vis[x] = i;
        bit(x+1);
    }
}

vector <int> find_roads(int n, vector <int> u, vector <int> v)
{
    lm = n, m = u.size();

    for(int i = 0; i < m; i++) U.pb(u[i]), V.pb(v[i]);

    bit(0);

    return arr;
}

Compilation message (stderr)

simurgh.cpp: In function 'void bit(int)':
simurgh.cpp:63:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         if(S.size() == 1 && trie.size() == lm-1) {
      |                             ~~~~~~~~~~~~^~~~~~~

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