oj.uz

Submission #706913

# Submission time Handle Problem Language Result Execution time Memory
706913 2023-03-08T06:34:56 Z vjudge1 ICC (CEOI16_icc) C++17
100 / 100
 117 ms 628 KB 
#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
#define pii pair<int,int>
#define fi first
#define se second
int s[2][maxn],sz[2],par[maxn],n;
vector<int> ver[maxn],ss[maxn],cur[2];
int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
void unions(int u,int v){
    u=findpar(u);v=findpar(v);
    par[v]=u;
    for(int x:ver[v]) ver[u].push_back(x);
    ver[v].clear();
}
void add(int t,int x){
    for(int v:ver[x]) s[t][sz[t]++]=v;
}
pii cal(){
    for(int i=0;i<n;i++) ss[i].clear();
    int len=1;
    for(int i=1;i<=n;i++){
        if(ver[i].empty()) continue;
        ss[0].push_back(i);
    }
    while(true){
        sz[0]=sz[1]=0;
        for(int i=0;i<len;i++){
            int ssz=(int)ss[i].size();
            for(int j=0;j<(ssz+1)/2;j++) add(0,ss[i][j]);
            for(int j=(ssz+1)/2;j<ssz;j++) add(1,ss[i][j]);
        }
        if(query(sz[0],sz[1],s[0],s[1])) break;
        int prelen=len;
        for(int i=0;i<prelen;i++){
            int ssz=(int)ss[i].size();
            if(ssz==1) continue;
            for(int j=(ssz+1)/2;j<ssz;j++){
                ss[len].push_back(ss[i].back());
                ss[i].pop_back();
            }
            len++;
        }
    }
    cur[0].clear();cur[1].clear();
    for(int i=0;i<sz[0];i++) cur[0].push_back(s[0][i]);
    for(int i=0;i<sz[1];i++) cur[1].push_back(s[1][i]);
    int l=0,r=sz[0]-1,f0=cur[0][0],f1=cur[1][0];
    while(l<r){
        int mid=(l+r)>>1;sz[0]=0;
        for(int i=l;i<=mid;i++) s[0][sz[0]++]=cur[0][i];
        if(query(sz[0],sz[1],s[0],s[1])) r=mid;
        else l=mid+1;
        f0=cur[0][l];
    }
    sz[0]=1;s[0][0]=f0;
    l=0;r=sz[1]-1;
    while(l<r){
        int mid=(l+r)>>1;sz[1]=0;
        for(int i=l;i<=mid;i++) s[1][sz[1]++]=cur[1][i];
        if(query(sz[0],sz[1],s[0],s[1])) r=mid;
        else l=mid+1;
        f1=cur[1][l];
    }
    return {f0,f1};
}
void run(int N){
    n=N;
    for(int i=1;i<=n;i++){ver[i].push_back(i);par[i]=i;}
    for(int i=1;i<n;i++){
        pii x=cal();
        setRoad(x.fi,x.se);
        unions(x.fi,x.se);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 94 queries used.
2 Correct 7 ms 500 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Ok! 532 queries used.
2 Correct 38 ms 500 KB Ok! 642 queries used.
3 Correct 40 ms 484 KB Ok! 625 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 500 KB Ok! 1421 queries used.
2 Correct 114 ms 492 KB Ok! 1600 queries used.
3 Correct 110 ms 628 KB Ok! 1618 queries used.
4 Correct 105 ms 492 KB Ok! 1494 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 492 KB Ok! 1439 queries used.
2 Correct 99 ms 492 KB Ok! 1417 queries used.
3 Correct 107 ms 496 KB Ok! 1563 queries used.
4 Correct 105 ms 500 KB Ok! 1511 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 512 KB Ok! 1556 queries used.
2 Correct 105 ms 620 KB Ok! 1519 queries used.
3 Correct 117 ms 492 KB Ok! 1602 queries used.
4 Correct 111 ms 488 KB Ok! 1568 queries used.
5 Correct 106 ms 468 KB Ok! 1463 queries used.
6 Correct 109 ms 492 KB Ok! 1549 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 496 KB Ok! 1587 queries used.
2 Correct 113 ms 492 KB Ok! 1609 queries used.