Submission #1280126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280126		enzy	Airline Route Map (JOI18_airline)	C++20	0 / 100	1526 ms	26388 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++) if(v[i].size()==N-2) pai=i;
    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) especial=i;
    }
    vector<int>bit;
    vector<pair<int,int>> 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);
        if(aux==8) bit_imp.push_back({v[x].size(),x});
        else bit_par.push_back({v[x].size(),x});
    }
    sort(bit_par.begin(),bit_par.end()); sort(bit_imp.begin(),bit_imp.end());
    reverse(bit_par.begin(),bit_par.end()); reverse(bit_imp.begin(),bit_imp.end());
    int cnt=0;
    for(pair<int,int> p : bit_par){
        int x=p.second;
        for(int y : v[x]) val[y]|=(1<<cnt);
        cnt+=2;
    }
    cnt=1;
    for(pair<int,int> p : bit_imp){
        int x=p.second;
        for(int y : v[x]) val[y]|=(1<<cnt);
        cnt+=2;
    }
    for(int x : bit) marc[x]++;
    marc[pai]++; marc[especial]++;
    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