oj.uz

Submission #940479

# Submission time Handle Problem Language Result Execution time Memory
940479 2024-03-07T09:46:51 Z parlimoos ICC (CEOI16_icc) C++14
100 / 100
 95 ms 856 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n;
int dsu[101];
vector<int> cs;
vector<arr(2)> sgs[10];
vector<int> dsuset[101];

void init(){
    fill(&dsu[0] , &dsu[n + 1] , -1);
    for(int i = 1 ; i <= n ; i++) cs.pb(i) , dsuset[i].pb(i);
}
int findDsu(int v){
    if(dsu[v] == -1) return v;
    return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
    a = findDsu(a) , b = findDsu(b);
    if((int)dsuset[a].size() < (int)dsuset[b].size()) swap(a , b);
    dsu[b] = a , cs.erase(lb(cs.bg() , cs.end() , b));
    for(int v : dsuset[b]) dsuset[a].pb(v);
}
int getSet(){
    int sz[2];
    for(int i = 0 ; i < 10 ; i++){
        sz[0] = 0 , sz[1] = 0;
        for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
            for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
                sz[(sg & 1)] += (int)dsuset[cs[v]].size();
            }
        }
        int a[sz[0]] , b[sz[1]];
        int cnt1 = 0 , cnt2 = 0;
        for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
            for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
                for(int u : dsuset[cs[v]]){
                    if((sg & 1)) b[cnt2++] = u;
                    else a[cnt1++] = u;
                }
            }
        }
        int d = query(sz[0] , sz[1] , a , b);
        if(d == 1) return i;
    }
}
arr(2) f(){
    for(int i = 0 ; i < 10 ; i++) sgs[i].cl();
    int c = (((int)cs.size() - 2) >> 1);
    sgs[0].pb({0 , c}) , sgs[0].pb({c + 1 , (int)cs.size() - 1});
    for(int i = 0 ; i < 9 ; i++){
        for(auto sg : sgs[i]){
            if(sg[0] == sg[1]) continue;
            else{
                c = (sg[0] + sg[1] - 1) >> 1;
                sgs[i + 1].pb({sg[0] , c}) , sgs[i + 1].pb({c + 1 , sg[1]});
            }
        }
    }
    int inx = getSet();
    vector<int> a , b;
    for(int sg = 0 ; sg < (int)sgs[inx].size() ; sg++){
        for(int v = sgs[inx][sg][0] ; v <= sgs[inx][sg][1] ; v++){
            for(int u : dsuset[cs[v]]){
                if((sg & 1)) b.pb(u);
                else a.pb(u);
            }
        }
    }
    int l = 0 , r = (int)a.size() - 1;
    while(r > l){
        int c = (l + r - 1) >> 1;
        int sz[2] = {c - l + 1 , (int)b.size()};
        int aa[sz[0]] , bb[sz[1]];
        for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[i];
        for(int i = 0 ; i < sz[0] ; i++) aa[i] = a[l + i];
        int d = query(sz[0] , sz[1] , aa , bb);
        if(d == 1) r = c;
        else l = c + 1;
    }
    int ans1 = l;
    l = 0 , r = (int)b.size() - 1;
    while(r > l){
        int c = (l + r - 1) >> 1;
        int sz[2] = {1 , c - l + 1};
        int aa[sz[0]] , bb[sz[1]];
        for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[l + i];
        aa[0] = a[ans1];
        int d = query(sz[0] , sz[1] , aa , bb);
        if(d == 1) r = c;
        else l = c + 1;
    }
    return {a[ans1] , b[l]};
}
void run(int N){
    n = N;
    init();
    for(int i = 1 ; i < n ; i++){
        arr(2) d = f();
        setRoad(d[0] , d[1]);
        uDsu(d[0] , d[1]);
    }
}

Compilation message

icc.cpp: In function 'int getSet()':
icc.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Ok! 101 queries used.
2 Correct 5 ms 624 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 852 KB Ok! 542 queries used.
2 Correct 29 ms 604 KB Ok! 640 queries used.
3 Correct 29 ms 600 KB Ok! 642 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 624 KB Ok! 1530 queries used.
2 Correct 89 ms 604 KB Ok! 1584 queries used.
3 Correct 89 ms 620 KB Ok! 1619 queries used.
4 Correct 88 ms 616 KB Ok! 1550 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 604 KB Ok! 1574 queries used.
2 Correct 90 ms 600 KB Ok! 1578 queries used.
3 Correct 95 ms 600 KB Ok! 1584 queries used.
4 Correct 85 ms 616 KB Ok! 1551 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 604 KB Ok! 1588 queries used.
2 Correct 89 ms 600 KB Ok! 1589 queries used.
3 Correct 93 ms 616 KB Ok! 1596 queries used.
4 Correct 89 ms 604 KB Ok! 1614 queries used.
5 Correct 87 ms 620 KB Ok! 1555 queries used.
6 Correct 87 ms 620 KB Ok! 1553 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 604 KB Ok! 1589 queries used.
2 Correct 95 ms 856 KB Ok! 1584 queries used.