oj.uz

Submission #1005671

# Submission time Handle Problem Language Result Execution time Memory
1005671 2024-06-22T18:05:57 Z alexdd ICC (CEOI16_icc) C++17
90 / 100
 82 ms 848 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);
        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! 96 queries used.
2 Correct 5 ms 604 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 600 KB Ok! 1435 queries used.
2 Correct 82 ms 848 KB Ok! 1665 queries used.
3 Correct 75 ms 600 KB Ok! 1592 queries used.
4 Correct 70 ms 600 KB Ok! 1521 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 620 KB Ok! 1466 queries used.
2 Correct 65 ms 600 KB Ok! 1445 queries used.
3 Correct 79 ms 600 KB Ok! 1638 queries used.
4 Correct 73 ms 628 KB Ok! 1530 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 604 KB Ok! 1630 queries used.
2 Correct 75 ms 624 KB Ok! 1623 queries used.
3 Correct 76 ms 624 KB Ok! 1641 queries used.
4 Correct 74 ms 628 KB Ok! 1601 queries used.
5 Correct 74 ms 624 KB Ok! 1496 queries used.
6 Correct 72 ms 600 KB Ok! 1566 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 600 KB Too many queries! 1627 out of 1625
2 Halted 0 ms 0 KB -