oj.uz

답안 #365502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365502 2021-02-11T18:30:12 Z valerikk 카멜레온의 사랑 (JOI20_chameleon) C++17
0 / 100
 22 ms 368 KB 
#include "chameleon.h"
#include <bits/stdc++.h> 
using namespace std;

int query(vector<int> p) {
    return Query(p);
}

void answer(int a, int b) {
    Answer(a, b);
}

const int N = 505;

vector<int> g[2 * N];
int color[2 * N];
vector<int> component[2];

void dfs(int u) {
    component[color[u]].push_back(u);
    for (int v : g[u]) {
        if (color[v] == -1) {
            color[v] = color[u] ^ 1;
            dfs(v);
        }
    }   
}

int my_query(int i, int j) {
    auto p = component[color[i]];
    p.push_back(j);
    return query(p);
}

void solve(int n) {
    vector<pair<int, int>> pairs;
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j < i; j++) {
            if (query(vector<int>{i, j}) == 1) 
                pairs.emplace_back(i, j);
        }
    }
    
    for (auto [i, j] : pairs) {
        g[i].push_back(j);
        g[j].push_back(i);
    }

    for (int i = 1; i <= 2 * n; i++) 
        color[i] = -1;
    for (int i = 1; i <= 2 * n; i++) {
        if (color[i] == -1) {
            color[i] = 0;
            dfs(i);
        }
    }

    for (auto [i, j] : pairs) {
        int ij = my_query(i, j), ji = my_query(j, i);
        if ((ij == n && ji == n) || (ij == n && ji == n - 1) || (ji == n && ij == n - 1)) 
            answer(i, j);
    }
}

void Solve(int N) {
    solve(N);
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 22 ms 364 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 22 ms 364 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -