oj.uz

Submission #379477

# Submission time Handle Problem Language Result Execution time Memory
379477 2021-03-18T10:00:06 Z dantoh000 Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 2 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#include "lokahia.h"
int Q[205][205];
const int LIM = 400;
vector<int> ord;
int tq = 0;
int query(int i, int j){
    if (i == j) return Q[i][i] = i;
    else if (tq >= LIM) return -1;
    else if (Q[i][j] == -2) {
        tq++;
        return Q[i][j] = Q[j][i] = CollectRelics(i,j);
    }
    else return Q[i][j];
}
int c[205];
int p[205];
int rk[205];
int sz[205];
void init(int n){
    for (int i = 0; i < n; i++){
        p[i] = i;
        rk[i] = 0;
        sz[i] = 1;
    }
}
int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
    x = find(x) , y= find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x,y);
    p[y] = x;
    sz[x] += sz[y];
    if (rk[x] == rk[y]) rk[x]++;
}
vector<ii> v;
int FindBase(int N){
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) Q[i][j] = -2;
    init(N);
    ord.resize(N);
    iota(ord.begin(), ord.end(), 0);
    random_shuffle(ord.begin(),ord.end());
    for (int i = 0; i < N/2; i++){
        int Q = query(ord[2*i],ord[2*i+1]);
        if (Q != -1){
            c[Q]+=2;
            un(Q, ord[2*i]);
            un(Q, ord[2*i+1]);
        }
        else{
            c[ord[2*i]]++;
            c[ord[2*i+1]]++;
        }
    }
    for (int i = 0; i < N; i++){
        if (c[i]) v.push_back({c[i],i});
    }
    sort(v.begin(),v.end());
    int st = v[0].second;
    vector<int> good, bad;
    for (auto x : v){
        if (find(x.second) != find(st)) good.push_back(x.second);
    }
    while (good.size() && tq <= LIM){
        sort(good.begin(),good.end());
        srand(time(NULL));
        random_shuffle(good.begin(),good.end());
        for (auto x : good){
            if (st == x) continue;
            int q = query(st,x);
            if (q != -1){
                if (q > st) st = q;
                un(st,q);
            }
            else bad.push_back(x);
        }
        if (sz[find(st)] > N/2) return st;
        vector<int> bad;
        good.clear();
        for (auto x : bad){
            good.push_back(x);
        }
        bad.clear();
    }
    return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Wrong
2 Incorrect 2 ms 748 KB Wrong
3 Correct 1 ms 620 KB Correct : C = 178
4 Incorrect 1 ms 748 KB Wrong
5 Incorrect 1 ms 748 KB Wrong
6 Incorrect 1 ms 620 KB Wrong
7 Incorrect 1 ms 748 KB Wrong
8 Incorrect 1 ms 748 KB Wrong
9 Correct 1 ms 620 KB Correct : C = 175
10 Correct 1 ms 748 KB Correct : C = 295
11 Correct 1 ms 620 KB Correct : C = 147
12 Correct 2 ms 748 KB Correct : C = 218
13 Correct 1 ms 748 KB Correct : C = 298
14 Incorrect 1 ms 620 KB Wrong
15 Incorrect 1 ms 748 KB Wrong
16 Correct 2 ms 748 KB Correct : C = 262
17 Incorrect 1 ms 620 KB Wrong
18 Incorrect 1 ms 492 KB Wrong
19 Correct 1 ms 748 KB Correct : C = 232
20 Incorrect 2 ms 748 KB Wrong
21 Incorrect 1 ms 620 KB Wrong
22 Incorrect 1 ms 620 KB Wrong
23 Incorrect 1 ms 620 KB Wrong
24 Incorrect 2 ms 748 KB Wrong
25 Correct 1 ms 748 KB Correct : C = 236
26 Correct 1 ms 620 KB Correct : C = 150
27 Correct 1 ms 748 KB Correct : C = 267