oj.uz

Submission #426957

# Submission time Handle Problem Language Result Execution time Memory
426957 2021-06-14T11:13:30 Z Runtime_error_ Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 296 KB 
/*
#include "simurgh.h"
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
using namespace std;
const int inf = 1e5+9,Q = 30000;
vector<int> cur,adj[inf],cp[inf],ask,ret;
int n,m,u[inf],v[inf],par[inf],cnt;
set<int> rets,roots;

int root(int x){
    if(par[x] == x)
        return x;
    return par[x] = root(par[x]);
}

bool join(int x,int y){
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;
    if(rand()%2)
        swap(x,y);
    par[x] = y;
    return 1;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {

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

    for(int x=0;x<n;x++){
        ask.clear();
        roots.clear();
        for(int i=0;i<n;i++)
            par[i] = i,cp[i].clear();
        for(int i=0;i<m;i++)
            if(u[i] != x && v[i] != x && join(u[i],v[i]))
                ask.pb(i);
        for(int i=0;i<m;i++){
            if(u[i] != x && v[i] != x)
                continue;
            int y = (u[i] ==x?v[i]:u[i]);
            y = root(y);
            roots.insert(y);
            cp[y].pb(i);
        }
        for(auto rt:roots){
            for(auto ort:roots)
                if(rt != ort)
                    ask.pb(cp[ort][0]);
            pi ans= pi(0,0);
            for(auto o:cp[rt]){
                ask.pb(o);
                assert(ask.size() == n-1);
                cnt++;
                assert(cnt < Q);
                ans = max(ans,pi(count_common_roads(ask),o));

                ask.pop_back();
            }
            for(auto ort:roots)
                if(rt != ort)
                    ask.pop_back();
           rets.insert(ans.second);
        }
    }
    for(auto o:rets)
        ret.pb(o);
    assert(count_common_roads(ret) == n-1);
    return ret;
}*/

#include "simurgh.h"
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
using namespace std;
const int inf = 1e5+9,Q = 30000;
int m,par[inf];
vector<int> ask;
int root(int x){
    if(par[x] == x)
        return x;
    return par[x] = root(par[x]);
}

bool join(int x,int y){
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;
    if(rand()%2)
        swap(x,y);
    par[x] = y;
    return 1;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {

    m = u.size();
    for(int mask = 0;mask < (1<<m);mask++){

        if(__builtin_popcount(mask) != n-1)continue;
        ask.clear();
        for(int j=0;j<m;j++)
            if(mask & (1<<j))
                ask.pb(j);
        for(int i=0;i<n;i++)
            par[i] = i;
        bool tr = 1;
        for(auto o:ask)
            if(!join(u[o],v[o]))
                tr = 0;
        if(tr && count_common_roads(ask) == n-1)
            return ask;
    }
}

/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 4 5
*/

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB correct
2 Correct 21 ms 204 KB correct
3 Correct 27 ms 296 KB correct
4 Correct 1 ms 292 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 2 ms 296 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 12 ms 296 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB correct
2 Correct 21 ms 204 KB correct
3 Correct 27 ms 296 KB correct
4 Correct 1 ms 292 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 2 ms 296 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 12 ms 296 KB correct
14 Execution timed out 3073 ms 204 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB correct
2 Correct 21 ms 204 KB correct
3 Correct 27 ms 296 KB correct
4 Correct 1 ms 292 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 2 ms 296 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 12 ms 296 KB correct
14 Execution timed out 3073 ms 204 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 204 KB correct
2 Execution timed out 3092 ms 204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB correct
2 Correct 21 ms 204 KB correct
3 Correct 27 ms 296 KB correct
4 Correct 1 ms 292 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 2 ms 296 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 12 ms 296 KB correct
14 Execution timed out 3073 ms 204 KB Time limit exceeded
15 Halted 0 ms 0 KB -