제출 #742229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742229		keta_tsimakuridze	카멜레온의 사랑 (JOI20_chameleon)	C++14	100 / 100	64 ms	596 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int Nn = 1000 + 5;
int vis[Nn];
vector<int> v[2], V[Nn];
void dfs(int u, int c) {
    vis[u] = c;
    v[c - 1].push_back(u);
    for(int i = 0; i < V[u].size(); i++) {
        if(!vis[V[u][i]]) dfs(V[u][i], 3 - c);
    }
}
int query(int t, int l, int r, int i) {
    vector<int> x; x.push_back(i);
    for(int i = l; i <= r; i++) x.push_back(v[t][i]);
    if(l > r) return 0;
    return (Query(x) < r - l + 1 + 1);
}
void Solve(int N) {
    for(int i = 2; i <= 2 * N; i++) {
        for(int j = 1; j < i; j++) vis[j] = 0;
        v[0].clear(); v[1].clear();
        for(int j = 1; j < i; j++) {
            if(!vis[j]) {
                dfs(j, 2);

            }
        }
        for(int t = 0; t < 2; t++) {
            int lo = 0, hi = (int)v[t].size() - 1;
            for(int c = 0; c < 3; c++) {
                if(!query(t, lo, hi, i)) break;
                int l = lo, r = hi, x = 0;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(!query(t, lo, mid, i)) l = mid + 1;
                    else r = mid - 1, x = mid;
                }

                V[i].push_back(v[t][x]);
                V[v[t][x]].push_back(i);
                lo = x + 1;
            }
        }
    }

    // 3nlogn + 4n + 6n
    set<pair<int,int>> s;
    for(int i = 1; i <= 2 * N; i++) {
        if(V[i].size() == 3) {
            for(int j = 0; j < 3; j++) {
                if(V[i][j] < i) s.insert({V[i][j], i});
            }
        }
    }
    for(int i = 1; i <= 2 * N; i++) {
//        cout << V[i].size() << endl;
        if(V[i].size() == 1) {
            if(V[i][0] < i) Answer(V[i][0], i);
            continue;
        }
        if(Query({i, V[i][1], V[i][2]}) == 1) {
            if(s.count({i, V[i][0]})) s.erase({i, V[i][0]});
            else s.erase({V[i][0], i});
            continue;
        }
        if(Query({i, V[i][0], V[i][2]}) == 1) {
            if(s.count({i, V[i][1]})) s.erase({i, V[i][1]});
            else s.erase({V[i][1], i});
            continue;
        }
        if(s.count({i, V[i][2]})) s.erase({i, V[i][2]});
        else s.erase({V[i][2], i});
    }
    while(s.size()) {
        Answer((*--s.end()).first, (*--s.end()).second);
        s.erase(--s.end());
    }
}

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'void dfs(int, int)':
chameleon.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36