Submission #1270787

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

Alice

#include "Alicelib.h"

#include <vector>
using namespace std;

namespace {
vector<pair<int, int> > graph;
}

void Alice(int N, int M, int A[], int B[])
{
	int V = N + 12;

	for (int i = 0; i < M; ++i) {
		graph.push_back({ A[i], B[i] });
	}
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j < N; ++j) {
			if ((j >> i) & 1) graph.push_back({ i + N, j });
		}
	}
	for (int i = 0; i < 10; ++i) graph.push_back({ i + N, 10 + N });
	for (int i = 1; i < 10; ++i) graph.push_back({ i - 1 + N, i + N });
	for (int i = 0; i < 10 + N; ++i) graph.push_back({ i, 11 + N });

	InitG(V, graph.size());
	for (int i = 0; i < graph.size(); ++i) {
		MakeG(i, graph[i].first, graph[i].second);
	}
}

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