Submission #1136853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136853		adaawf	Airline Route Map (JOI18_airline)	C++20	0 / 100	170 ms	21852 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
vector<int> g[2005];
void Alice(int n, int m, int a[], int b[]) {
    for (int i = 0; i < m; i++) {
        g[a[i]].push_back(b[i]);
    }
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < n; j++) {
            if (j & (1 << i)) {
                g[n + i].push_back(j);
            }
        }
    }
    for (int i = 0; i < n + 10; i++) {
        g[n + 11].push_back(i);
    }
    for (int i = 0; i < 10; i++) {
        g[n + 10].push_back(n + i);
    }
    for (int i = 0; i < 9; i++) {
        g[n + i].push_back(n + i + 1);
    }
    int c = 0;
    for (int i = 0; i < n + 12; i++) {
        c = c + g[i].size();
    }
    InitG(n + 12, c);
    c = 0;
    for (int i = 0; i < n + 12; i++) {
        for (int w : g[i]) {
            MakeG(c, i, w);
            c++;
        }
    }
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
vector<int> g[2005];
int dd[2005][2005], res[2005], da[2005];
void Bob(int n, int m, int a[], int b[]) {
    for (int i = 0; i < m; i++) {
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        dd[a[i]][b[i]] = dd[b[i]][a[i]] = 1;
    }
    int h = 0, k = 0;
    for (int i = 0; i < n; i++) {
        if (g[i].size() > g[h].size()) {
            h = i;
        }
    }
    for (int i = 0; i < n; i++) {
        if (dd[h][i] == 0 && h != i) {
            k = i;
            break;
        }
    }
    for (int w : g[k]) da[w] = 1;
    int l = 0, ll = -1;
    for (int w : g[k]) {
        int c = 0;
        for (int ww : g[w]) {
            if (da[ww] == 1) {
                c++;
            }
        }
        if (c == 1) {
            l = w;
            break;
        }
    }
    return;
    vector<int> vv;
    vv.push_back(l);
    while (1) {
        int fl = 0;
        for (int w : g[l]) {
            if (w == ll || da[w] == 0) continue;
            ll = l;
            l = w;
            vv.push_back(w);
            fl = 1;
        }
        if (fl == 0) break;
    }
    da[h] = da[k] = 1;
    if (g[vv[0]].size() < g[vv.back()].size()) {
        reverse(vv.begin(), vv.end());
    }
    for (int i = 0; i < vv.size(); i++) {
        for (int ww : g[vv[i]]) {
            if (da[ww]) continue;
            res[ww] += (1 << i);
        }
    }
    vector<pair<int, int>> v;
    for (int i = 0; i < m; i++) {
        if (da[a[i]] == 0 && da[b[i]] == 0) {
            v.push_back({res[a[i]], res[b[i]]});
        }
    }
    InitMap(n - 12, v.size());
    for (auto w : v) {
        MakeMap(w.first, w.second);
    }
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 15
• Subtask 3: 0 / 63