oj.uz

답안 #1005669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005669 2024-06-22T18:03:51 Z alexdd CEOI16_icc (CEOI16_icc) C++17
7 / 100
 228 ms 616 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)
{
    bool gasit=1;
    int cva[2],cvb[2];
    for(int i=0;i<cntv;i++)
    {
        for(int j=0;j<cntu;j++)
        {
            cva[0]=v[i];
            cvb[0]=u[j];
            if(query(1,1,cva,cvb))
            {
                return v[i];
            }
        }
    }
    if(!gasit) while(1);
    int st,dr,ans;
    st=0;
    dr=cntv-2;
    ans=cntv-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(query(mij,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

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 600 KB Ok! 1134 queries used.
2 Correct 45 ms 604 KB Ok! 1160 queries used.

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 604 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 228 ms 616 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 612 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 604 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 604 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -