oj.uz

Submission #475741

# Submission time Handle Problem Language Result Execution time Memory
475741 2021-09-23T23:51:46 Z soba Carnival (CEOI14_carnival) C++14
100 / 100
 47 ms 328 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int par[151], siz[151];
int fnd(int node)
{
    if(par[node]!=node)
    {
        return par[node]=fnd(par[node]);
    }
    return par[node]=node;
}
void uni(int a, int b)
{
    a=fnd(a);
    b=fnd(b);
    if(a==b)
        return;
    if(siz[a]>siz[b])
    {
        par[b]=a;
        siz[a]++;
    }
    else
    {
        par[a]=b;
        siz[b]++;
    }
    return ;
}
int main()
{
    int n;
    cin >> n;
    int start=1 , nxt , q;
    for(int i =1 ; i<= n ;i++)
    {
        siz[i]=1;
        par[i]=i;
    }
    int head[151] , had, expected=2 , hh;
    for(int i =2 ; i<= n ; i++)
    {
        //cout << expected << "\n";
        cout << i << " ";
        for(int j =1 ; j<= i ; j++)
        {
            cout << j << " ";
        }
        cout << "\n";
        cout.flush();
        cin >> had;
        if(had==expected)
        {
            head[i]++;
            expected++;
            //cout << "here\n";
            continue;
        }
        hh=1;
        for(int j = 2 ; j< i ; j++)
        {
            if(!head[j])continue;
            cout << 2 << " " << i << " " << j << "\n";
            cout.flush();
            cin >> q ;
            if(q==1)
            {
                uni(i , j);
                hh=j;
                break;
            }
        }
        if(hh==1)
        {
            uni(i,1);
        }
        expected=had+1;
    }
    int cnt=1;
    map<int,int>mp;
    for(int i =1 ; i<=n ; i++)
    {
        q=fnd(i);
        if(mp[q]==0)mp[q]=cnt++;
    }
    cout << 0 << " ";
    for(int i =1 ; i<=n ; i++)
    {
        q=fnd(i);
        cout <<mp[q] << " ";
    }
    cout <<"\n";
    cout.flush();
}

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:36:9: warning: unused variable 'start' [-Wunused-variable]
   36 |     int start=1 , nxt , q;
      |         ^~~~~
carnival.cpp:36:19: warning: unused variable 'nxt' [-Wunused-variable]
   36 |     int start=1 , nxt , q;
      |                   ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 200 KB Output is correct
2 Correct 31 ms 200 KB Output is correct
3 Correct 20 ms 200 KB Output is correct
4 Correct 7 ms 296 KB Output is correct
5 Correct 6 ms 200 KB Output is correct
6 Correct 5 ms 200 KB Output is correct
7 Correct 17 ms 200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 200 KB Output is correct
2 Correct 15 ms 200 KB Output is correct
3 Correct 9 ms 200 KB Output is correct
4 Correct 10 ms 272 KB Output is correct
5 Correct 5 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 11 ms 200 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 10 ms 200 KB Output is correct
3 Correct 47 ms 272 KB Output is correct
4 Correct 4 ms 292 KB Output is correct
5 Correct 6 ms 200 KB Output is correct
6 Correct 4 ms 200 KB Output is correct
7 Correct 25 ms 272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 10 ms 200 KB Output is correct
3 Correct 13 ms 272 KB Output is correct
4 Correct 5 ms 288 KB Output is correct
5 Correct 6 ms 328 KB Output is correct
6 Correct 4 ms 292 KB Output is correct
7 Correct 25 ms 200 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 200 KB Output is correct
2 Correct 15 ms 200 KB Output is correct
3 Correct 18 ms 272 KB Output is correct
4 Correct 27 ms 272 KB Output is correct
5 Correct 5 ms 296 KB Output is correct
6 Correct 11 ms 200 KB Output is correct
7 Correct 9 ms 292 KB Output is correct