Submission #644276

#	Time	Username	Problem	Language	Result	Execution time	Memory
644276		valerikk	Airline Route Map (JOI18_airline)	C++17	100 / 100	740 ms	25912 KiB

Alice

#include "Alicelib.h"
#include <assert.h>
#include <stdio.h>
#include <vector>

using namespace std;

void Alice(int N, int M, int A[], int B[]) {
    vector<pair<int, int>> edges;

    for (int i = 0; i < M; ++i) {
        edges.push_back({A[i], B[i]});
    }
    
    for (int i = 0; i < N + 10; ++i) {
        edges.push_back({N + 10, i});
    }
    
    for (int i = 0; i < 10; ++i) {
        edges.push_back({N + 11, N + i});
    }

    edges.push_back({N + 1, N + 3});
    for (int i = 0; i < 9; ++i) {
        edges.push_back({N + i, N + i + 1});
    }

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

    InitG(N + 12, edges.size());

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

Bob

#include "Boblib.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

namespace {

const int MAXV = 1 << 10;
 
bool e[MAXV][MAXV];
int deg[MAXV];
int deg0[MAXV];
int val[MAXV];
int id[MAXV];
bool used[MAXV];

void dfs(int v, vector<int> &path) {
    used[v] = true;
    path.push_back(v);
    for (int u = 0; u < MAXV; ++u) {
        if (!used[u] && val[u] == 0 && (deg0[v] < 3 || deg0[u] < 3) && e[v][u]) 
            dfs(u, path);
    }
}

}

void Bob(int V, int U, int C[], int D[]) {
    for (int i = 0; i < U; ++i) {
        ++deg[C[i]];
        ++deg[D[i]];
        e[C[i]][D[i]] = e[D[i]][C[i]] = true;
    }

    memset(val, 255, sizeof val);

    int s = -1;
    int cnt = 0;
    for (int i = 0; i < V; ++i) {
        if (deg[i] == V - 2) {
            ++cnt;
            for (int j = 0; j < V; ++j) {
                if (j != i && !e[i][j])
                    s = j;
            }
            val[i] = -2;
            val[s] = -2;
        }
    }

    for (int i = 0; i < V; ++i) {
        if (i != s && e[s][i])
            val[i] = 0;
    }

    int s0 = -1;
    for (int i = 0; i < V; ++i) {
        if (val[i] == 0) {
            for (int j = 0; j < V; ++j) {
                if (j != i && val[j] == 0 && e[i][j])
                    ++deg0[i];
            }
            if (deg0[i] == 1) 
                s0 = i;
        }
    }

    vector<int> path;
    dfs(s0, path);

    if (!e[path[1]][path[3]])
        reverse(path.begin(), path.end());

    for (int i = 0; i < V; ++i) {
        if (val[i] == -1) {
            id[i] = -1;
            for (int j = 0; j < 10; ++j) {
                if (e[i][path[j]]) 
                    id[i] += 1 << j;
            }
        }
    }

    vector<pair<int, int>> edges;
    for (int i = 0; i < U; ++i) {
        if (val[C[i]] == -1 && val[D[i]] == -1)
            edges.push_back({id[C[i]], id[D[i]]});
    }

    // for (int i = 0; i < edges.size(); ++i) {
    //     printf("%d %d\n", edges[i].first, edges[i].second);
    // }

    InitMap(V - 12, edges.size());

    for (int i = 0; i < edges.size(); ++i) {
        MakeMap(edges[i].first, edges[i].second);
    }
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < edges.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < edges.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

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