제출 #243646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243646		osaaateiasavtnl	Meetings (JOI19_meetings)	C++14	29 / 100	3083 ms	16504 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

const int N = 2007;

int par[N];
int link[N];

int mem[N][N];
int Query(int u, int v) {
    if (mem[u][v] != -1)
        return mem[u][v];
    return mem[u][v] = mem[v][u] = Query(0, u, v);
}   

bool used[N];

void Solve(int n) {

    memset(used, 0, sizeof used);

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            mem[i][j] = -1;
                
    for (int i = 1; i < n; ++i)
        par[i] = -1;
          
    queue <int> q;
    q.push(0);
    while (q.size()) {
        int u = q.front(); q.pop();
        used[u] = 1;

        auto check = [&](int v) {
            for (int i = 0; i < n; ++i) {
                if (mem[i][v] == i && !used[i])
                    return 0;
            }   
            return 1;
        };   

        vector <int> cur;                                
        for (int v = 0; v < n; ++v) {
            if (par[v] == -1 && link[u] == link[v]) {
                vector <bool> del(cur.size());
                bool ban = 0;
                for (int i = 0; i < cur.size(); ++i) {
                    int x = Query(v, cur[i]);
                    if (x == v) {
                        del[i] = 1;
                        link[cur[i]] = v;
                        continue;
                    }   
                    if (x == cur[i]) {
                        link[v] = cur[i];
                        ban = 1;
                        break;
                    }
                }   
                if (!ban) {
                    vector <int> a = {v};                    
                    link[v] = v;
                    for (int i = 0; i < cur.size(); ++i) {
                        if (!del[i])
                            a.app(cur[i]);
                    }
                    cur = a;
                }
            }
        }

        for (int i = 0; i < n; ++i)
            while (link[link[i]] != link[i])
                link[i] = link[link[i]];

        for (int v : cur) {
            par[v] = u;            
            q.push(v);
        }   
    }   

    for (int i = 1; i < n; ++i) {
        int u = i;
        int v = par[i];
        if (v < u)
            swap(u, v);

        #ifdef HOME
        cout << "edge " << u << ' ' << v << endl;
        #endif

        Bridge(u,v);
    }   
}

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

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:59:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < cur.size(); ++i) {
                                 ~~^~~~~~~~~~~~
meetings.cpp:75:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < cur.size(); ++i) {
                                     ~~^~~~~~~~~~~~
meetings.cpp:46:14: warning: variable 'check' set but not used [-Wunused-but-set-variable]
         auto check = [&](int v) {
              ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71