oj.uz

Submission #1005672

# Submission time Handle Problem Language Result Execution time Memory
1005672 2024-06-22T18:07:13 Z alexdd ICC (CEOI16_icc) C++17
100 / 100
 99 ms 852 KB 
#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> comp[105];
vector<int> con[105];
int cntc;
bool visited[105];
void dfs(int nod, int c)
{
    visited[nod]=1;
    comp[c].push_back(nod);
    for(auto adj:con[nod])
        if(!visited[adj])
            dfs(adj,c);
}
int a[105],b[105],cnta,cntb;
int gaseste(int v[], int cntv, int u[], int cntu)
{
    int st,dr,ans;
    st=0;
    dr=cntv-2;
    ans=cntv-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(query(mij+1,cntu,v,u))
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return v[ans];
}
void run(int N)
{
    for(int pas=1;pas<N;pas++)
    {
        for(int i=1;i<=N;i++) visited[i]=0;
        cntc=0;
        for(int i=1;i<=N;i++)
        {
            if(!visited[i])
            {
                comp[cntc].clear();
                dfs(i,cntc);
                cntc++;
            }
        }
        bool gasit=0;
        for(int i=0;(1<<i)<cntc;i++)
        {
            cnta=cntb=0;
            for(int j=0;j<cntc;j++)
            {
                if(((1<<i)&j))
                {
                    for(auto x:comp[j]) a[cnta++]=x;
                }
                else
                {
                    for(auto x:comp[j]) b[cntb++]=x;
                }
            }
            if(query(cnta,cntb,a,b))
            {
                gasit=1;
                break;
            }
        }
        assert(gasit);
        random_shuffle(a,a+cnta);
        random_shuffle(b,b+cntb);
        int x = gaseste(a,cnta,b,cntb);
        int y = gaseste(b,cntb,a,cnta);
        setRoad(x,y);
        con[x].push_back(y);
        con[y].push_back(x);
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Ok! 527 queries used.
2 Correct 25 ms 600 KB Ok! 674 queries used.
3 Correct 25 ms 604 KB Ok! 661 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 604 KB Ok! 1426 queries used.
2 Correct 77 ms 616 KB Ok! 1613 queries used.
3 Correct 77 ms 852 KB Ok! 1564 queries used.
4 Correct 62 ms 600 KB Ok! 1515 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 640 KB Ok! 1492 queries used.
2 Correct 75 ms 600 KB Ok! 1534 queries used.
3 Correct 99 ms 628 KB Ok! 1595 queries used.
4 Correct 70 ms 604 KB Ok! 1461 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 600 KB Ok! 1600 queries used.
2 Correct 76 ms 620 KB Ok! 1618 queries used.
3 Correct 74 ms 628 KB Ok! 1624 queries used.
4 Correct 76 ms 600 KB Ok! 1596 queries used.
5 Correct 72 ms 604 KB Ok! 1498 queries used.
6 Correct 76 ms 620 KB Ok! 1554 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 600 KB Ok! 1604 queries used.
2 Correct 79 ms 600 KB Ok! 1609 queries used.