제출 #1171017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171017		anteknne	Meetings (JOI19_meetings)	C++20	0 / 100	1285 ms	9208 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int MAXN = 2000;
int wyn[MAXN][MAXN];

bool jest[MAXN];
int ile[MAXN];
vector<int> liscie;
vector<int> sciezka;

void Solve(int n) {
    for (int i = 1; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            wyn[i][j] = Query(0, i, j);
            wyn[j][i] = wyn[i][j];
        }
    }

    for (int i = 0; i < n; i ++) {
        jest[i] = true;
    }

    for (int i = 1; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            ile[wyn[i][j]] ++;
        }
    }

    for (int i = 0; i < n; i ++) {
        if (ile[i] == 0) {
            liscie.pb(i);
        }
    }

    while (!liscie.empty()) {
        int v = liscie.back();
        liscie.pop_back();
        if (!jest[v] || v == 0) {
            continue;
        }
        jest[v] = false;
        //cout << "============" << "\n";
        //cout << v << "\n";

        for (int i = 0; i < n; i ++) {
            ile[i] = 0;
        }

        for (int i = 0; i < n; i ++) {
            if (i != 0 && i != v && jest[i]) {
                ile[wyn[i][v]] ++;
            }
        }

        sciezka.clear();

        for (int i = 0; i < n; i ++) {
            if (ile[i] > 0) {
                sciezka.pb(i);
            }
        }

        for (int i = 0; i < n; i ++) {
            ile[i] = 0;
        }

        int m = int(sciezka.size());

        /*for (auto x : sciezka) {
            cout << x << ' ';
        }*/
        //cout << "\n";

        if (m <= 2) {
            Bridge(min(sciezka.back(), v), max(sciezka.back(), v));
            //cout << sciezka.back() << " " << v << "\n";
        } else {

            for (int i = 1; i < m; i ++) {
                for (int j = i + 1; j < m; j ++) {
                    ile[wyn[sciezka[i]][sciezka[j]]] ++;
                }
            }

            for (int i = 0; i < m; i ++) {
                if (ile[sciezka[i]] == 0 && sciezka[i] != 0) {
                    Bridge(min(sciezka[i], v), max(sciezka[i], v));
                    //cout << sciezka[i] << " " << v << "\n";
                }
            }

        }






        for (int i = 0; i < n; i ++) {
            ile[i] = 0;
        }
        for (int i = 1; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                if (jest[i] && jest[j]) {
                    ile[wyn[i][j]] ++;
                }
            }
        }


        for (int i = 0; i < n; i ++) {
            if (ile[i] == 0 && jest[i]) {
                liscie.pb(i);
            }
        }


    }


}

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