Submission #1280148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280148		enzy	Airline Route Map (JOI18_airline)	C++20	0 / 100	212 ms	26272 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
void Alice( int n, int m, int A[], int B[] ){
	int sb=0, cnt=0;
	for(int i=0;i<n;i++)
	    for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
	InitG(n+12,m+n+20+sb+9);
	for(int i=0;i<m;i++) MakeG(cnt++,A[i],B[i]);
	for(int i=0;i<=n+10;i++) if(i!=n) MakeG(cnt++,n,i);
	for(int i=n+1;i<=n+10;i++) MakeG(cnt++,n+11,i);
	for(int i=0;i<n;i++)
	    for(int k=0;k<10;k++) if(i&(1<<k)) MakeG(cnt++,i,n+k+1);
	for(int i=1;i<=8;i+=2) MakeG(cnt++,n+i,n+i+2);
	MakeG(cnt++,n+9,n+1);
	for(int i=2;i<=8;i+=2) MakeG(cnt++,n+i,n+i+2);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1020;
vector<int>v[maxn];
int val[maxn], marc[maxn];
int arestas[maxn][maxn];
int dfs(int u, int lim){
    marc[u]++;
    int ret=0;
    for(int viz : v[u]){
        if(viz==lim||arestas[viz][lim]==0) continue;
        if(marc[viz]){
            ret++;
            continue;
        }
        ret++;
        ret+=dfs(viz,lim);
    }
    return ret;
}
void Bob( int N, int M, int C[], int D[] ){
	for(int i=0;i<M;i++){
	    arestas[C[i]][D[i]]=arestas[D[i]][C[i]]=1;
	    v[C[i]].push_back(D[i]);
	    v[D[i]].push_back(C[i]);
	}
	int n=N-12;
	int sb=0;
	for(int i=0;i<n;i++)
	    for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
    int m=M-n-20-sb-9;
    InitMap(n,m);
    int pai;
    for(int i=0;i<N;i++){
        sort(v[i].begin(),v[i].end());
        //cout << i << " " << v[i].size() << ": ";
        //for(int x : v[i]) cout << x << " ";
        //cout << endl;
        if(v[i].size()==N-2) pai=i;
    }
    //cout << endl;
    //cout << "! " << pai << endl;
    v[pai].push_back(maxn);
    int especial;
    for(int i=0;i<N;i++){
        int aux=lower_bound(v[pai].begin(),v[pai].end(),i)-v[pai].begin();
        if(v[pai][aux]!=i&&i!=pai) especial=i;
    }
    //cout << "!! " << especial << endl;
    vector<int>bit, bit_par, bit_imp;
    for(int x : v[especial]) bit.push_back(x);
    for(int x : bit){
        memset(marc,0,sizeof(marc));
        int aux=dfs(x,especial);
        //cout << aux << " ";
        if(aux==8) bit_imp.push_back(x);
        else bit_par.push_back(x);
    }
    for(int x : bit) marc[x]++;
    marc[pai]++; marc[especial]++;
    //cout << endl;
    //cout << bit.size() << " " << bit_par.size() << " " << bit_imp.size() << endl;
    bool ja=false;
    sort(bit_par.begin(),bit_par.end()); 
    int qtd=0, me=maxn;
    do{
        if(ja) break;
        sort(bit_imp.begin(),bit_imp.end());
        do{
            qtd++;
            if(ja) break;
            memset(val,0,sizeof(val));
            int cnt=0, ma=0;
            for(int x : bit_par){
                for(int y : v[x]){
                    val[y]|=(1<<cnt);
                    if(!marc[y]) ma=max(ma,val[y]);
                }
                cnt+=2;
            }
            cnt=1;
            for(int x : bit_imp){
                for(int y : v[x]){
                    val[y]|=(1<<cnt);
                    if(!marc[y]) ma=max(ma,val[y]);
                }
                cnt+=2;
            }
            me=min(me,ma);
            if(ma==n-1) ja=true;
        }while(next_permutation(bit_imp.begin(),bit_imp.end()));
    }while(next_permutation(bit_par.begin(),bit_par.end()));
    //if(ja) cout << "yay" << endl;
    //else cout << qtd << " " << me << " nah" << endl;
    for(int i=0;i<N;i++){
        if(marc[i]) continue;
        for(int x : v[i]) if(x>i&&marc[x]==0) MakeMap(val[x],val[i]);
    }
}

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