Submission #48561

#	Time	Username	Problem	Language	Result	Execution time	Memory
48561		ngkan146	Airline Route Map (JOI18_airline)	C++11	0 / 100	693 ms	30888 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> GG[1505];
void Alice(int n, int m, int a[], int b[]){
    for(int i=0;i<m;i++){
        GG[a[i]+1].push_back(b[i]+1);
        GG[b[i]+1].push_back(a[i]+1);
    }

    for(int i=1;i<=n;i++){
        for(int bit=0;bit<10;bit++){
            if (((i>>bit) & 1))
                GG[i].push_back(n+bit+1),
                GG[n+bit+1].push_back(i);
        }
    }
    // num 11
    for(int i=n+1;i<=n+10;i++){
        GG[n+11].push_back(i);
        GG[i].push_back(n+11);
    }
    // num 12
    for(int i=1;i<=n+10;i++){
        GG[i].push_back(n+12);
        GG[n+12].push_back(i);
    }

    for(int i=1;i<=9;i++){
        GG[n+i].push_back(n+i+1);
        GG[n+i+1].push_back(i);
    }
    for(int i=2;i<=8;i++){
        GG[n+i].push_back(n+10);
        GG[n+10].push_back(n+i);
    }

    int numV = n+12;
    int numE = 0;
    for(int i=1;i<=n+12;i++){
        numE += GG[i].size();
    }
    InitG(numV, numE/2);
    numE = 0;
    for(int i=1;i<=n+12;i++){
        for(auto v: GG[i]){
            if (i < v)
                MakeG(numE++, i-1, v-1);
        }
    }
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

vector <int> G[1505];
int isbit[1505];
int num[15];
vector <int> Gbit[1505];
set <int> s;
int mask[1505];
void Bob( int n, int m, int C[], int D[] ){
    for(int i=0;i<m;i++){
        G[C[i]+1].push_back(D[i]+1);
        G[D[i]+1].push_back(C[i]+1);
    }
    // find num 12
    for(int i=1;i<=n;i++){
        if (G[i].size() == n-2)
            num[12] = i;
    }
    // find num11
    for(int i=1;i<=n;i++){
        if (i == num[12]) continue;
        bool ok = 1;
        for(auto v: G[i])
            ok &= (v != num[12]);
        if (ok)
            num[11] = i;
    }
    // find lst;
    vector <int> bitlst;
    for(auto v: G[num[11]]){
        if (v != num[12]){
            isbit[v] = 1;
            bitlst.push_back(v);
        }
    }

    for(auto u: bitlst){
        for(auto v:G[u]){
            if (!isbit[v])  continue;
            Gbit[u].push_back(v);
        }
    }
    // find num1
    for(auto v: bitlst){
        if (Gbit[v].size() == 2)
            num[1] = v;
    }
    // find num2 -> 9
    for(int cur=1;cur<9;cur++){
        for(auto v: Gbit[num[cur]]){
            if (v != num[cur] && G[v].size() < 9){
                num[cur+1] = v;
            }
        }
    }
    set <int> used;
    for(int i=1;i<=12;i++){
        if (i != 10)    used.insert(num[i]);
    }

    // find num 10
    for(auto v: bitlst){
        if (!used.count(v)){
            num[10] = v;
            used.insert(v);
        }
    }

    for(int i=1;i<=10;i++){
        for(auto v: G[num[i]]){
            if (!used.count(v))
                mask[v] |= (1<<(i-1));
        }
    }
    int newV = n - 12;
    int newE = 0;
    for(int i=1;i<=n;i++){
        if (!mask[i])   continue;
        for(auto v: G[i]){
            newE += (!mask[v]);
        }
    }

	InitMap( newV, newE/2 );

	for(int i=1;i<=n;i++){
        if (!mask[i])  continue;
        for(auto v: G[i]){
            if (!mask[i])  continue;
            if (mask[i] < mask[v])
                MakeMap(mask[i]-1, mask[v]-1);
        }
	}
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:18:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (G[i].size() == n-2)
             ~~~~~~~~~~~~^~~~~~

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