oj.uz

Submission #407002

# Submission time Handle Problem Language Result Execution time Memory
407002 2021-05-18T10:08:10 Z doowey Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 51 ms 536 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));
        }
    }
}

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

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);
        fin(i, qa, 0, (int)qa.size() - 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 'void fin(int, std::vector<int>, int, int)':
chameleon.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     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 34 ms 536 KB Output is correct
4 Correct 33 ms 496 KB Output is correct
5 Correct 39 ms 484 KB Output is correct
6 Correct 33 ms 456 KB Output is correct
7 Correct 34 ms 456 KB Output is correct
8 Correct 33 ms 456 KB Output is correct
9 Correct 39 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 200 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 200 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 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Incorrect 51 ms 404 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 34 ms 536 KB Output is correct
4 Correct 33 ms 496 KB Output is correct
5 Correct 39 ms 484 KB Output is correct
6 Correct 33 ms 456 KB Output is correct
7 Correct 34 ms 456 KB Output is correct
8 Correct 33 ms 456 KB Output is correct
9 Correct 39 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 200 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 328 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Incorrect 51 ms 404 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -