Submission #1270802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270802		tvgk	Airline Route Map (JOI18_airline)	C++20	0 / 100	1392 ms	27104 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 20;

vector<ii> ed;

void Alice(int n, int m, int a[], int b[])
{
	for (int i = 0; i < m; i++)
        ed.push_back({a[i], b[i]});

    for (int j = 0; j < 10; j++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((i >> j) & 1)
                ed.push_back({i, n + j});
        }
        ed.push_back({n + j, n + 10});

        if (j)
            ed.push_back({n + j, n + j - 1});
    }

    for (int i = 0; i < n + 10; i++)
        ed.push_back({n + 11, i});

    InitG(n + 12, ed.size());
    m = 0;
    for (ii i : ed)
        MakeG(m++, i.fi, i.se);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 20;

vector<int> par, w[mxN];
bool vis[mxN];
int spe[mxN], val[mxN];

void Find(int j)
{
    par.push_back(j);
    spe[j] = 1;

    for (int i : w[j])
    {
        if (spe[i] == 3)
            Find(i);
    }
}

void Bob(int n, int m, int a[], int b[])
{
	for (int i = 0; i < m; i++)
    {
        w[a[i]].push_back(b[i]);
        w[b[i]].push_back(a[i]);
    }

    for (int i = 0; i < n; i++)
    {
        if (w[i].size() == n - 2)
        {
            spe[i] = 1;
            vis[i] = 1;
            for (int j : w[i])
                vis[j] = 1;
            break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            spe[i] = 1;
            for (int j : w[i])
                spe[j] = 2;
        }
    }

    for (int i = 0; i < m; i++)
    {
        if (spe[a[i]] >= 2 && spe[b[i]] >= 2)
            spe[a[i]] = 3;
    }

    for (int i = 0; i < n; i++)
    {
        if (spe[i] == 2)
            Find(i);
    }
    if (w[par[0]].size() < w[par.back()].size())
        reverse(par.begin(), par.end());

    for (int i = 0; i < par.size(); i++)
    {
        for (int j : w[par[i]])
            val[j] += (1 << i);
    }

    vector<ii> ans;
    for (int i = 0; i < m; i++)
    {
        if (spe[a[i]] || spe[b[i]])
            continue;

        ans.push_back({val[a[i]], val[b[i]]});
    }

    InitMap(n - 12, ans.size());
    for (ii i : ans)
    {
        cerr << i.fi << " " << i.se << '\n';
        MakeMap(i.fi, i.se);
    }

}

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