Submission #260460

#	Time	Username	Problem	Language	Result	Execution time	Memory
260460		mhy908	Airline Route Map (JOI18_airline)	C++14	100 / 100	1128 ms	31008 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;

static int re;
static pii edg[2000010];

void Alice(int N, int M, int A[], int B[]){
    int v=N+12;
    for(int i=0; i<M; i++)edg[++re]=mp(A[i], B[i]);
    for(int i=0; i<10; i++){
        for(int j=0; j<N; j++){
            if(j&(1<<i))edg[++re]=mp(N+i, j);
        }
    }
    for(int i=N; i<=N+9; i++)edg[++re]=mp(i, N+10);
    for(int i=0; i<=N+9; i++)edg[++re]=mp(i, N+11);
    for(int i=N; i<N+9; i++)edg[++re]=mp(i, i+1);
    InitG(v, re);
    for(int i=1; i<=re; i++)MakeG(i-1, edg[i].F, edg[i].S);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;

static int ch[1510];
static vector<int> link[1510];
static pii ans[2000010], arr[100];
static int tmp;

int num[1510];

void Bob(int V, int U, int C[], int D[]){
	int n, m=0;
	for(int i=0; i<U; i++){
        link[C[i]].eb(D[i]);
        link[D[i]].eb(C[i]);
	}
	int maxx=0, maxnum;
	for(int i=0; i<V; i++){
        int sz=link[i].size();
        if(maxx<sz){
            maxx=sz;
            maxnum=i;
        }
	}
	ch[maxnum]=1;
	for(auto i:link[maxnum])ch[i]=2;
	int st, st2;
	for(int i=0; i<V; i++){
        if(ch[i])continue;
        if(link[i].size()==10)st2=i;
	}
	ch[st2]=1;
	int mindeg=1e9;
	for(auto i:link[st2]){
        if(mindeg>link[i].size()){
            mindeg=link[i].size();
            st=i;
        }
        ch[i]=0;
	}
	for(int i=9; ; i--){
        for(auto j:link[st]){
            if(ch[j]!=2)continue;
            num[j]+=(1<<i);
        }
        if(i==0)break;
        ch[st]=1;
        for(auto j:link[st]){
            if(!ch[j]){
                st=j;
                break;
            }
        }
	}
	for(int i=0; i<U; i++){
        if(ch[C[i]]==2&&ch[D[i]]==2){
            ans[++tmp]=mp(num[C[i]], num[D[i]]);
        }
	}
	InitMap(V-12, tmp);
	for(int i=1; i<=tmp; i++)MakeMap(ans[i].F, ans[i].S);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mindeg>link[i].size()){
            ~~~~~~^~~~~~~~~~~~~~~
Bob.cpp:18:6: warning: unused variable 'n' [-Wunused-variable]
  int n, m=0;
      ^
Bob.cpp:18:9: warning: unused variable 'm' [-Wunused-variable]
  int n, m=0;
         ^
Bob.cpp: At global scope:
Bob.cpp:12:26: warning: 'arr' defined but not used [-Wunused-variable]
 static pii ans[2000010], arr[100];
                          ^~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:31:12: warning: 'maxnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ch[maxnum]=1;
  ~~~~~~~~~~^~
Bob.cpp:33:6: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int st, st2;
      ^~
Bob.cpp:33:10: warning: 'st2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int st, st2;
          ^~~

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