Submission #1280557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280557		enzy	Airline Route Map (JOI18_airline)	C++20	100 / 100	185 ms	30264 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>arestas;
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+10+sb+9+10);
	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=n+2;i<=n+10;i++) MakeG(cnt++,i-1,i);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1020;
vector<int>v[maxn];
int val[maxn], marc[maxn], freq[maxn];
int arestas[maxn][maxn];
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-11-sb-9-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;
    }
    int at=-1, best=0;
    for(int x : v[especial]) freq[x]++;
    for(int x : v[especial]){
        int qtd=0;
        for(int y : v[x]) qtd+=freq[y];
        if(qtd==1&&v[x].size()>best){
            at=x;
            best=v[x].size();
        } 
    }    
    //cout << "!! " << especial << endl;
    marc[especial]++; marc[pai]++;
    for(int i=0;i<10;i++){
        marc[at]++;
        for(int x : v[at]) val[x]|=(1<<i);
        int nxt;
        for(int viz : v[at]){
            if(!marc[viz]&&freq[viz]) nxt=viz;
        }
        at=nxt;
    }
    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: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63