oj.uz

Submission #407003

# Submission time Handle Problem Language Result Execution time Memory
407003 2021-05-18T10:12:02 Z doowey Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 56 ms 592 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int n;

const int N = 1001;
vector<int> E[N];

bool vis[N];
vector<int> pa, qa;

void dfs(int u, int bit){
    vis[u]=true;
    if(bit == 0){
        pa.push_back(u);
    }
    else{
        qa.push_back(u);
    }
    for(auto x : E[u]){
        if(!vis[x]){
            dfs(x, (bit ^ 1));
        }
    }
}

int fin(int node, vector<int> ss, int lf, int rf, int need){
    vector<int> party;
    party.push_back(node);
    for(int i = lf; i <= rf; i ++ ){
        party.push_back(ss[i]);
    }
    if(need){
        int Q = Query(party);
        if(party.size() == Q){
            return 0;
        }
    }
    if(lf == rf){
        E[node].push_back(ss[lf]);
        E[ss[lf]].push_back(node);
        return 1;
    }
    int mid = (lf + rf) / 2;
    int half = fin(node, ss, lf, mid, 1);
    fin(node, ss, mid + 1, rf, half);
    return 1;
}

map<pii, int> lovely;

void add(int la, int lb){
    lovely[mp(la, lb)] = 1;
    lovely[mp(lb, la)] = 1;
}

void Solve(int _n) {
    n = _n;
    for(int i = 2; i <= 2 * n; i ++ ){
        for(int j = 1; j < i ; j ++ ){
            vis[j]=false;
        }
        pa.clear();
        qa.clear();
        for(int j = 1; j < i ; j ++ ){
            if(!vis[j]){
                dfs(j, 0);
            }
        }
        fin(i, pa, 0, (int)pa.size() - 1, 1);
        fin(i, qa, 0, (int)qa.size() - 1, 1);
    }
    int X, Y, Z;
    int n0, n1, n2;
    for(int i = 1; i <= 2 * n; i ++ ){
        if(E[i].size() == 3){
            X = E[i][0];
            Y = E[i][1];
            Z = E[i][2];
            n0 = Query({i, X, Y});
            n1 = Query({i, X, Z});
            n2 = Query({i, Y, Z});
            if(n0 == 2 && n1 == 2){
                add(i, X);
            }
            else if(n0 == 2 && n2 == 2){
                add(i, Y);
            }
            else{
                add(i, Z);
            }
        }
    }
    for(int i = 1; i <= 2 * n; i ++ ){
        for(auto x : E[i]){
            if(x > i && !lovely.count(mp(i, x))){
                Answer(i, x);
            }
        }
    }
}

Compilation message

chameleon.cpp: In function 'int fin(int, std::vector<int>, int, int, int)':
chameleon.cpp:44:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if(party.size() == Q){
      |            ~~~~~~~~~~~~~^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 29 ms 536 KB Output is correct
4 Correct 32 ms 508 KB Output is correct
5 Correct 29 ms 456 KB Output is correct
6 Correct 30 ms 592 KB Output is correct
7 Correct 30 ms 536 KB Output is correct
8 Correct 30 ms 508 KB Output is correct
9 Correct 30 ms 456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 2 ms 328 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 2 ms 328 KB Output is correct
17 Correct 2 ms 328 KB Output is correct
18 Correct 2 ms 328 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Incorrect 56 ms 440 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 29 ms 536 KB Output is correct
4 Correct 32 ms 508 KB Output is correct
5 Correct 29 ms 456 KB Output is correct
6 Correct 30 ms 592 KB Output is correct
7 Correct 30 ms 536 KB Output is correct
8 Correct 30 ms 508 KB Output is correct
9 Correct 30 ms 456 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 2 ms 328 KB Output is correct
23 Correct 2 ms 328 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 2 ms 328 KB Output is correct
26 Correct 2 ms 328 KB Output is correct
27 Correct 2 ms 328 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Incorrect 56 ms 440 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -