oj.uz

Submission #296981

# Submission time Handle Problem Language Result Execution time Memory
296981 2020-09-11T06:26:59 Z Trickster Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 512 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 368 KB correct
2 Correct 1113 ms 504 KB correct
3 Correct 1142 ms 376 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 34 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 16 ms 256 KB correct
13 Correct 1139 ms 376 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 368 KB correct
2 Correct 1113 ms 504 KB correct
3 Correct 1142 ms 376 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 34 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 16 ms 256 KB correct
13 Correct 1139 ms 376 KB correct
14 Execution timed out 3032 ms 512 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 368 KB correct
2 Correct 1113 ms 504 KB correct
3 Correct 1142 ms 376 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 34 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 16 ms 256 KB correct
13 Correct 1139 ms 376 KB correct
14 Execution timed out 3032 ms 512 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Incorrect 469 ms 380 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 368 KB correct
2 Correct 1113 ms 504 KB correct
3 Correct 1142 ms 376 KB correct
4 Correct 5 ms 384 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 34 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 384 KB correct
9 Correct 1 ms 256 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 1 ms 384 KB correct
12 Correct 16 ms 256 KB correct
13 Correct 1139 ms 376 KB correct
14 Execution timed out 3032 ms 512 KB Time limit exceeded
15 Halted 0 ms 0 KB -