Submission #166309

#	Time	Username	Problem	Language	Result	Execution time	Memory
166309		georgerapeanu	Airline Route Map (JOI18_airline)	C++11	37 / 100	1024 ms	30664 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#pragma once
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 1e3;
const int LGMAX = 10;

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] + 1,b[i] + 1});
    }

    for(int h = 0;h < LGMAX;h++){
        for(int i = 1;i <= n;i++){
            if((i >> h) & 1){
                edges.push_back({i,n + 1 + h});
            }
        }
    }

    int lst = n + LGMAX;
    for(int i = n + 1;i <= n + LGMAX;i++){
        for(int j = i + 1;j <= lst;j++){
            edges.push_back({i,j});
        }
        lst--;
    }

    for(int i = n + 1;i <= n + LGMAX;i++){
        edges.push_back({n + LGMAX + 1,i});
    }

    edges.push_back({n + LGMAX + 2,n + LGMAX + 1});

    InitG(n + LGMAX + 2,edges.size());

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

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#pragma once
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e3;
const int LGMAX = 10;

static int gr[NMAX + LGMAX + 5];
static vector<int> graph[NMAX + LGMAX + 5];
int exp_gr[LGMAX + 2];
int tag[NMAX + LGMAX + 5];

void Bob( int n, int m, int a[], int b[] ){
	for(int i = 0;i < m;i++){
        gr[a[i] + 1]++;
        gr[b[i] + 1]++; 
        graph[a[i] + 1].push_back(b[i] + 1);
        graph[b[i] + 1].push_back(a[i] + 1);
    }

    for(int h = 0;h < LGMAX;h++){
        exp_gr[h]++;
        for(int i = 1;i <= n - LGMAX - 2;i++){
            if((i >> h) & 1){
                exp_gr[h]++;
            }
        }
    }

    int lst = LGMAX - 1;

    for(int h = 0;h < LGMAX;h++){
        for(int i = h;i <= lst;i++){
            exp_gr[h]++;
            exp_gr[i]++;
        }
        lst--;
    }
    
    sort(exp_gr,exp_gr + LGMAX);
    reverse(exp_gr,exp_gr + LGMAX);


    int master_node = -1;
    int control_node = -1;

    for(int i = 1;i <= n;i++){
        if(gr[i] == 1){
            int node = graph[i][0];
            if(gr[node] != LGMAX + 1){
                continue;
            }

            for(int i = 0;i < (int)graph[node].size();i++){
                if(graph[node][i] == node){
                    swap(graph[node][i],graph[node].back());
                    break;
                }
            }

            sort(graph[node].begin(),graph[node].begin() + LGMAX,[&](int a,int b){return gr[a] > gr[b];});
            
            for(int i = 0;i < LGMAX;i++){
                if(exp_gr[i] != gr[graph[node][i]]){
                    continue;
                }
            }
            control_node = i;
            master_node = node;
            break;
        }
    }

    assert(master_node != -1 && control_node != -1);

    for(int i = 0;i < (int)graph[master_node].size();i++){
        if(graph[master_node][i] == control_node){
            swap(graph[master_node][i],graph[master_node].back());
            break;
        }
    }

    sort(graph[master_node].begin(),graph[master_node].begin() + LGMAX,[&](int a,int b){return gr[a] > gr[b];});
            
    tag[master_node] = -1;
    tag[control_node] = -1;

    for(int i = 0;i < LGMAX;i++){
        tag[graph[master_node][i]] = -1;
    }

    for(int i = 0;i < LGMAX;i++){
        for(auto it:graph[graph[master_node][i]]){
            if(tag[it] != -1){
                tag[it] |= (1 << i);
            }
        }
    }

    vector<pair<int,int> > edges;

    for(int i = 0;i < m;i++){
        if(tag[a[i] + 1] != -1 && tag[b[i] + 1] != -1){
            edges.push_back({tag[a[i] + 1],tag[b[i] + 1]});
        }
    }

    InitMap(n - LGMAX - 2,edges.size());

    for(auto it:edges){
        MakeMap(it.first - 1,it.second - 1);
    }
}

Compilation message (stderr)

Alice.cpp:4:9: warning: #pragma once in main file
 #pragma once
         ^~~~

Bob.cpp:4:9: warning: #pragma once in main file
 #pragma once
         ^~~~

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