Submission #1173594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173594		anmattroi	Airline Route Map (JOI18_airline)	C++17	0 / 100	157 ms	21888 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

void Alice(int N, int M, int A[], int B[]){
    vector<vector<int> > adj(N+12);

    int cnt = M;

    for (int i = 0; i < M; i++)
        adj[A[i]].emplace_back(B[i]);

    for (int i = N; i < N+10 - 1; i++) {
        adj[i].emplace_back(i+1);
        ++cnt;
    }
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 10; j++) if (i>>j&1) {
            adj[N+j].emplace_back(i);
            ++cnt;
        }

    for (int i = 0; i < N; i++) {
        adj[N+10].emplace_back(i);
        ++cnt;
    }
    adj[N+10].emplace_back(N+11);
    ++cnt;

    InitG(N+12, cnt);

    cnt = 0;
    for (int i = 0; i < N+12; i++)
        for (int j : adj[i]) {
            MakeG(cnt, i, j);
//            cerr << i << ' ' << j << "\n";
            cnt++;
        }
}

/*
4 3
0 1
1 2
1 3
*/

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;

void Bob( int V, int U, int C[], int D[] ){
    vector<vector<int> > adj(V, vector<int>(V, 0));
	vector<int> deg(V, 0);
	for (int i = 0; i < U; i++) {
        ++deg[C[i]]; ++deg[D[i]];
        adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
	}
    int p1 = -1, p2 = -1;
    for (int i = 0; i < V; i++) if (deg[i] == V-11) {
        p1 = i;
        break;
    }
    for (int i = 0; i < V; i++)
    if (deg[i] == 1 && adj[p1][i]) {
        p2 = i;
        break;
    }


    vector<int> old_graph;
    int start_of_chain = -1;

    for (int i = 0; i < V; i++)
    if (adj[p1][i] && i != p2) {
        old_graph.emplace_back(i);
    } else if (!adj[p1][i] && deg[i] == 1) start_of_chain = i;


    int old = -1;
    vector<int> chain(1, start_of_chain);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < V; j++) if (j != old && adj[start_of_chain][j] && !adj[p1][j]) {
            old = start_of_chain;
            start_of_chain = j;
            chain.emplace_back(j);
            break;
        }
    }
    if (deg[chain[0]] < deg[chain.back()]) reverse(chain.begin(), chain.end());

    vector<pair<int, int> > edges;


    for (int i = 0; i < U; i++) {
        int a = C[i], b = D[i];
        if (adj[p1][a] && a != p2 && adj[p1][b] && b != p2) {
            int m1 = 0, m2 = 0;
            for (int j = 0; j < 10; j++) if (adj[chain[j]][a]) m1 += (1<<j);
            for (int j = 0; j < 10; j++) if (adj[chain[j]][b]) m2 += (1<<j);
            edges.emplace_back(m1, m2);
        }
    }
    InitMap(old_graph.size(), edges.size());
    for (int i = 0; i < edges.size(); i++) MakeMap(edges[i].first, edges[i].second);

}


/*
4 3
0 1
1 2
1 3
*/

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