oj.uz

Submission #328506

# Submission time Handle Problem Language Result Execution time Memory
328506 2020-11-16T19:00:14 Z JovanK26 ICC (CEOI16_icc) C++14
100 / 100
 178 ms 660 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int prt[101];
int sz[101];
int ask(vector<int> a,vector<int> b)
{
    int n=a.size();
    int m=b.size();
    int a1[n];
    int b1[m];
    for(int i=0;i<n;i++)
    {
        a1[i]=a[i];
    }
    for(int i=0;i<m;i++)
    {
        b1[i]=b[i];
    }
    return query(n,m,a1,b1);
}
void sett(int n)
{
    for(int i=1;i<=n;i++)
    {
        prt[i]=i;
        sz[i]=1;
    }
}
int findd(int x)
{
    while(x!=prt[x])
    {
        prt[x]=prt[prt[x]];
        x=prt[x];
    }
    return x;
}
void unionn(int x,int y)
{
    x=findd(x);
    y=findd(y);
    if(x==y)return;
    if(sz[x]<sz[y])swap(x,y);
    prt[y]=x;
    sz[x]+=sz[y];
}
void run(int n)
{
    sett(n);
    int rez1,rez2;
    for(int i=0;i<n-1;i++)
    {
        vector< vector<int> > g(n+1);
        for(int j=1;j<=n;j++)
        {
            g[findd(j)].push_back(j);
        }
        vector< vector<int> > cur;
        for(int j=1;j<=n;j++)
        {
            if(!g[j].empty())
            {
                cur.push_back(g[j]);
            }
        }
        vector<int> v1,v2;
        for(int bit=8;bit>=0;bit--)
        {
            if((1<<bit)>=cur.size())continue;
            vector<int> t1,t2;
            for(int j=0;j<cur.size();j++)
            {
                if(j&(1<<bit))
                {
                    for(auto x : cur[j])
                    {
                        t1.push_back(x);
                    }
                }
                else
                {
                    for(auto x : cur[j])
                    {
                        t2.push_back(x);
                    }
                }
            }
            if(t1.empty() || t2.empty())continue;
            if(ask(t1,t2))
            {
                v1=t1;
                v2=t2;
                break;
            }
        }
        int l=0;
        int r=v1.size()-1;
        int m;
        while(l<r)
        {
           m=(l+r)/2;
           vector<int> temp;
           for(int i=0;i<=m;i++)
           {
               temp.push_back(v1[i]);
           }
           if(ask(temp,v2))
           {
               r=m;
           }
           else
           {
               l=m+1;
           }
        }
        rez1=v1[l];
        l=0;
        r=v2.size()-1;
        while(l<r)
        {
           m=(l+r)/2;
           vector<int> temp;
           for(int i=0;i<=m;i++)
           {
               temp.push_back(v2[i]);
           }
           if(ask(v1,temp))
           {
               r=m;
           }
           else
           {
               l=m+1;
           }
        }
        rez2=v2[l];
        setRoad(rez1,rez2);
        unionn(rez1,rez2);
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if((1<<bit)>=cur.size())continue;
      |                ~~~~~~~~^~~~~~~~~~~~
icc.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int j=0;j<cur.size();j++)
      |                         ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 492 KB Ok! 107 queries used.
2 Correct 8 ms 492 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 492 KB Ok! 540 queries used.
2 Correct 54 ms 620 KB Ok! 637 queries used.
3 Correct 55 ms 572 KB Ok! 627 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 660 KB Ok! 1334 queries used.
2 Correct 176 ms 492 KB Ok! 1579 queries used.
3 Correct 170 ms 492 KB Ok! 1526 queries used.
4 Correct 169 ms 620 KB Ok! 1499 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 620 KB Ok! 1461 queries used.
2 Correct 167 ms 492 KB Ok! 1503 queries used.
3 Correct 170 ms 492 KB Ok! 1513 queries used.
4 Correct 155 ms 492 KB Ok! 1377 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 492 KB Ok! 1507 queries used.
2 Correct 168 ms 588 KB Ok! 1505 queries used.
3 Correct 174 ms 584 KB Ok! 1566 queries used.
4 Correct 176 ms 492 KB Ok! 1529 queries used.
5 Correct 158 ms 492 KB Ok! 1419 queries used.
6 Correct 178 ms 492 KB Ok! 1579 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 624 KB Ok! 1543 queries used.
2 Correct 168 ms 492 KB Ok! 1500 queries used.