Submission #1270781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270781		tvgk	Airline Route Map (JOI18_airline)	C++20	0 / 100	678 ms	65260 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;

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

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

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

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

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

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

    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);
    }

    for (int i = 0; i < n; i++)
    {
        if (spe[i])
            continue;

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

    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)
        MakeMap(i.fi, i.se);
}

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