oj.uz

Submission #278018

# Submission time Handle Problem Language Result Execution time Memory
278018 2020-08-21T08:51:32 Z MKopchev Chameleon's Love (JOI20_chameleon) C++14
24 / 100
 48 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;

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

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

    if(other.size()==1)
    {
        add_edge(original,other[0]);
        return;
    }

    vector<int> le={},ri={};

    for(int i=0;i<other.size();i++)
        if(i%2==0)le.push_back(other[i]);
        else ri.push_back(other[i]);

    go(original,le);
    go(original,ri);
}
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]);
    }
}

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);

                    break;
                }
        }
}

Compilation message

chameleon.cpp: In function 'void go(int, std::vector<int>)':
chameleon.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(Query(help)==help.size())return;
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<other.size();i++)
      |                 ~^~~~~~~~~~~~~

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 36 ms 512 KB Output is correct
4 Correct 38 ms 504 KB Output is correct
5 Correct 37 ms 504 KB Output is correct
6 Correct 37 ms 512 KB Output is correct
7 Correct 37 ms 504 KB Output is correct
8 Correct 43 ms 512 KB Output is correct
9 Correct 37 ms 504 KB Output is correct

Subtask #2
20.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 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

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 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 2 ms 384 KB Wrong Answer [5]
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 48 ms 504 KB Wrong Answer [3]
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 36 ms 512 KB Output is correct
4 Correct 38 ms 504 KB Output is correct
5 Correct 37 ms 504 KB Output is correct
6 Correct 37 ms 512 KB Output is correct
7 Correct 37 ms 504 KB Output is correct
8 Correct 43 ms 512 KB Output is correct
9 Correct 37 ms 504 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 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 376 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Incorrect 2 ms 384 KB Wrong Answer [5]
22 Halted 0 ms 0 KB -