oj.uz

Submission #869537

# Submission time Handle Problem Language Result Execution time Memory
869537 2023-11-04T16:41:41 Z velislavgarkov ICC (CEOI16_icc) C++14
100 / 100
 106 ms 652 KB 
#include "icc.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e2+10;
int n;
int par[MAXN], p[MAXN];
vector <int> v[MAXN];
int subs[2][MAXN], sub_ind[2];
int pref[MAXN], lev[16][MAXN], cnt_lev[16], maxl;
int qa[MAXN], qb[MAXN];
int index_v[MAXN];
bool used[MAXN];
int qabr, qbbr, br;
int root(int x) {
    if (par[x]==x) return x;
    return par[x]=root(par[x]);
}
void add(int ind, int i) {
    for (auto j:v[index_v[i]]) {
        subs[ind][sub_ind[ind]]=j;
        sub_ind[ind]++;
    }
}
/*
int find_middle(int ql, int qr) {
    if (ql+1==qr) return ql;
    int l, r, mid;
    l=ql; r=qr;
    while (l<r) {
        mid=(l+r)/2;
        if ((pref[mid]-pref[ql-1])*2<=pref[qr]-pref[ql-1]) l=mid+1;
        else r=mid;
    }
    return l-1;
}*/
void build_levels(int level, int l, int r) {
    lev[level][cnt_lev[level]]=r-l+1;
    cnt_lev[level]++;
    if (l>=r) return;
    maxl=max(maxl,level);
    int mid=(l+r)/2;
    build_levels(level+1,l,mid);
    build_levels(level+1,mid+1,r);
}
void find_subsets() {
    int level=1, cur_ind;
    for (int i=0;i<12;i++) cnt_lev[i]=0;
    pref[0]=0;
    for (int i=1;i<br;i++) pref[i]=pref[i-1]+v[index_v[i]].size();
    maxl=0;
    build_levels(0,1,br-1);
    while (level<=maxl) {
        cur_ind=1;
        sub_ind[0]=sub_ind[1]=0;
        for (int i=0;i<cnt_lev[level];i++) {
            for (int j=0;j<lev[level][i];j++,cur_ind++) add(i%2,cur_ind);
        }
        if (query(sub_ind[0],sub_ind[1],subs[0],subs[1])) return;
        level++;
    }
    sub_ind[0]=sub_ind[1]=0;
    for (int i=1;i<br;i++) add(i%2,i);
}
int find_vertex(int i, int j) {
    qbbr=sub_ind[j];
    for (int k=0;k<sub_ind[j];k++) qb[k]=subs[j][k];
    int l, r, mid;
    l=0; r=sub_ind[i]-1;
    while (l<r) {
        qabr=0;
        mid=(l+r)/2;
        for (int k=l;k<=mid;k++) {
            qa[qabr]=subs[i][k];
            qabr++;
        }
        if (query(qabr,qbbr,qa,qb)) r=mid;
        else l=mid+1;
    }
    return subs[i][l];
}
void run(int N) {
    n=N;
    for (int i=1;i<=n;i++) par[i]=i;
    int cnt=0;
    while (cnt<n-1) {
        for (int i=1;i<=n;i++) {
            if (!v[i].empty()) v[i].clear();
        }
        for (int i=1;i<=n;i++) {
            p[i]=root(i);
            v[p[i]].push_back(i);
        }
        br=1;
        for (int i=1;i<=n;i++) {
            if (v[i].empty()) continue;
            index_v[br]=i;
            br++;
        }
        random_shuffle(index_v+1,index_v+br);
        find_subsets();
        random_shuffle(subs[0],subs[0]+sub_ind[0]);
        random_shuffle(subs[1],subs[1]+sub_ind[1]);
        
        int ansa=find_vertex(0,1);
        int ansb=find_vertex(1,0);
        setRoad(ansa,ansb);
        par[root(ansa)]=root(ansb);
        cnt++;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 97 queries used.
2 Correct 4 ms 604 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 604 KB Ok! 515 queries used.
2 Correct 26 ms 604 KB Ok! 618 queries used.
3 Correct 26 ms 644 KB Ok! 612 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 600 KB Ok! 1386 queries used.
2 Correct 87 ms 636 KB Ok! 1577 queries used.
3 Correct 86 ms 604 KB Ok! 1458 queries used.
4 Correct 79 ms 600 KB Ok! 1473 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 600 KB Ok! 1483 queries used.
2 Correct 83 ms 652 KB Ok! 1481 queries used.
3 Correct 90 ms 628 KB Ok! 1543 queries used.
4 Correct 82 ms 600 KB Ok! 1419 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 624 KB Ok! 1522 queries used.
2 Correct 83 ms 600 KB Ok! 1543 queries used.
3 Correct 86 ms 600 KB Ok! 1563 queries used.
4 Correct 82 ms 604 KB Ok! 1539 queries used.
5 Correct 86 ms 624 KB Ok! 1442 queries used.
6 Correct 82 ms 628 KB Ok! 1519 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 624 KB Ok! 1545 queries used.
2 Correct 84 ms 612 KB Ok! 1548 queries used.