Submission #768205

#	Time	Username	Problem	Language	Result	Execution time	Memory
768205		AdamGS	Airline Route Map (JOI18_airline)	C++17	100 / 100	526 ms	24724 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
void Alice(int n, int m, int A[], int B[]) {
	if(n==1) {
		InitG(1, 0);
		return;
	}
	vector<pair<int,int>>kraw;
	rep(i, m) kraw.pb({A[i], B[i]});
	rep(i, n) rep(j, 10) if(i&(1<<j)) kraw.pb({i, n+j});
	rep(i, 9) kraw.pb({n+i, n+i+1});
	rep(i, n+10) kraw.pb({i, n+10});
	rep(i, 10) kraw.pb({n+i, n+11});
	InitG(n+12, kraw.size());
	rep(i, kraw.size()) MakeG(i, kraw[i].st, kraw[i].nd);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1020;
int deg[LIM], czy[LIM], typ[LIM], deg2[LIM], odw[LIM], nr[LIM];
void Bob(int v, int u, int C[], int D[]) {
	if(v==1) {
		InitMap(1, 0);
		return;
	}
	rep(i, u) {
		++deg[C[i]];
		++deg[D[i]];
	}
	int jaki=-1;
	rep(i, v) if(deg[i]==v-2) jaki=i;
	typ[jaki]=1;
	rep(i, u) {
		if(C[i]==jaki) czy[D[i]]=1;
		if(D[i]==jaki) czy[C[i]]=1;
	}
	int jaki2=-1;
	rep(i, v) if(i!=jaki && !czy[i]) jaki2=i;
	typ[jaki2]=2;
	rep(i, u) {
		if(C[i]==jaki2) typ[D[i]]=3;
		if(D[i]==jaki2) typ[C[i]]=3;
	}
	rep(i, u) if(typ[C[i]]==3 && typ[D[i]]==3) {
		++deg2[C[i]];
		++deg2[D[i]];
	}
	vector<int>kand;
	rep(i, v) if(typ[i]==3 && deg2[i]==1) kand.pb(i);
	if(deg[kand[0]]<deg[kand[1]]) swap(kand[0], kand[1]);
	int akt=kand[0];
	rep(i, 10) {
		odw[akt]=1;
		int nast=-1;
		rep(j, u) {
			if(C[j]==akt && !typ[D[j]]) nr[D[j]]+=1<<i;
			if(D[j]==akt && !typ[C[j]]) nr[C[j]]+=1<<i;
			if(C[j]==akt && typ[D[j]]==3 && !odw[D[j]]) nast=D[j];
			if(D[j]==akt && typ[C[j]]==3 && !odw[C[j]]) nast=C[j];
		}
		akt=nast;
	}
	vector<pair<int,int>>kraw;
	rep(i, u) if(!typ[C[i]] && !typ[D[i]]) kraw.pb({nr[C[i]], nr[D[i]]});
	InitMap(v-12, kraw.size());
	rep(i, kraw.size()) MakeMap(kraw[i].st, kraw[i].nd);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
Alice.cpp:21:2: note: in expansion of macro 'rep'
   21 |  rep(i, kraw.size()) MakeG(i, kraw[i].st, kraw[i].nd);
      |  ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
Bob.cpp:56:2: note: in expansion of macro 'rep'
   56 |  rep(i, kraw.size()) MakeMap(kraw[i].st, kraw[i].nd);
      |  ^~~

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