oj.uz

Submission #278040

# Submission time Handle Problem Language Result Execution time Memory
278040 2020-08-21T09:10:54 Z MKopchev Chameleon's Love (JOI20_chameleon) C++14
4 / 100
 68 ms 512 KB 
#include "chameleon.h"
#include<bits/stdc++.h>

using namespace std;

const int nmax=1e3+42;

vector< pair<int,int> > edges;

vector<int> adj[nmax];

int n_;

int colour[nmax];

void dfs(int node,int col)
{
    if(colour[node]!=-1)return;
    colour[node]=col;

    for(auto k:adj[node])
        dfs(k,!col);
}

void add_edge(int u,int v)
{
    //cout<<"edge "<<u<<" "<<v<<endl;

    adj[u].push_back(v);
    adj[v].push_back(u);
}
void go(int original,vector<int> other)
{
    if(other.size()==0)return;

    while(1)
    {
        vector<int> help=other;
        help.push_back(original);

        if(Query(help)==help.size())return;

        //there is an edge
        vector<int> active=other;

        while(active.size()>1)
        {
            vector<int> groups[2]={{},{}};

            for(int i=0;i<active.size();i++)
                groups[i%2].push_back(active[i]);

            groups[0].push_back(original);

            if(Query(groups[0])==groups[0].size())active=groups[1];
            else
            {
                groups[0].pop_back();
                active=groups[0];
            }

        }

        add_edge(original,active[0]);

        vector<int> other_new={};
        for(auto k:other)
            if(k!=active[0])other_new.push_back(k);

        other=other_new;
    }
}
void make()
{
    for(int i=1;i<=2*n_;i++)
    {
        memset(colour,-1,sizeof(colour));

        for(int j=1;j<i;j++)
            if(colour[j]==-1)dfs(j,0);

        vector<int> groups[2]={{},{}};

        for(int j=1;j<i;j++)
            groups[colour[j]].push_back(j);

        go(i,groups[0]);
        go(i,groups[1]);

        //cout<<"--- "<<query_count<<endl;
    }
}

int love[nmax];

bool solved[nmax];

set<int> blocked[nmax];

void Solve(int N)
{
    n_=N;

    make();

    for(int i=1;i<=2*n_;i++)
        if(solved[i]==0)
        {
            if(adj[i].size()==1)
            {
                Answer(i,adj[i][0]);
                solved[i]=1;
                solved[adj[i][0]]=1;
            }
            else
            {
                if(Query({i,adj[i][0],adj[i][1]})==1)love[i]=adj[i][2];
                else if(Query({i,adj[i][0],adj[i][2]})==1)love[i]=adj[i][1];
                else love[i]=adj[i][0];

                blocked[i].insert(love[i]);
                blocked[love[i]].insert(i);
            }
        }

    for(int i=1;i<=2*n_;i++)
        if(solved[i]==0)
        {
            for(auto k:adj[i])
                if(blocked[i].count(k)==0)
                {
                    solved[i]=1;
                    solved[k]=1;

                    Answer(i,k);
                }
        }
}

Compilation message

chameleon.cpp: In function 'void go(int, std::vector<int>)':
chameleon.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(Query(help)==help.size())return;
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int i=0;i<active.size();i++)
      |                         ~^~~~~~~~~~~~~~
chameleon.cpp:55:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             if(Query(groups[0])==groups[0].size())active=groups[1];
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 34 ms 512 KB Output is correct
4 Correct 32 ms 384 KB Output is correct
5 Correct 33 ms 504 KB Output is correct
6 Correct 32 ms 512 KB Output is correct
7 Correct 33 ms 504 KB Output is correct
8 Correct 33 ms 504 KB Output is correct
9 Correct 37 ms 508 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 68 ms 504 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 34 ms 512 KB Output is correct
4 Correct 32 ms 384 KB Output is correct
5 Correct 33 ms 504 KB Output is correct
6 Correct 32 ms 512 KB Output is correct
7 Correct 33 ms 504 KB Output is correct
8 Correct 33 ms 504 KB Output is correct
9 Correct 37 ms 508 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Incorrect 0 ms 384 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -