Submission #655662

#	Time	Username	Problem	Language	Result	Execution time	Memory
655662		haojiandan	Airline Route Map (JOI18_airline)	C++14	100 / 100	675 ms	29092 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define MP make_pair

vector<pair<int,int> > ans;
void add(int x,int y) {
	ans.push_back(MP(x,y));
}
};

void Alice( int n, int m, int A[], int B[] ) {
	for (int i=n;i<=n+9;i++) for (int j=0;j<n;j++) if (j>>(i-n)&1) add(i,j);
	for (int i=0;i<m;i++) add(A[i],B[i]);
	int s=n+10,t=n+11;
	for (int i=0;i<s;i++) add(i,s);
	for (int i=n;i<n+9;i++) add(i,i+1);
	for (int i=n;i<=n+9;i++) add(t,i);
	InitG(t+1,(int)ans.size());
	for (int i=0;i<ans.size();i++) MakeG(i,ans[i].first,ans[i].second);
}

Bob

#include "Boblib.h"

#include <bits/stdc++.h>
using namespace std;
namespace {
#define MP make_pair
const int maxn=1020;
int id[maxn],G[maxn][maxn];
bool mk[maxn],H[maxn];
int Deg[maxn],deg[maxn];
vector<int> vec[maxn];
vector<int> V;
void DFS(int x,int p) {
	V.push_back(x);
	for (int &y : vec[x]) if (y!=p) DFS(y,x);
}
vector<pair<int,int> > ans;
void add(int x,int y) { ans.push_back(MP(x,y)); }
};

void Bob( int N, int M, int C[], int D[] ){

	int n=N-12;
	if (n==1) { InitMap(1,0); return; }
	for (int i=0;i<M;i++) {
		deg[C[i]]++,deg[D[i]]++;
		G[C[i]][D[i]]=G[D[i]][C[i]]=1;
	}
	int s=-1,t=-1;
	for (int i=0;i<N;i++) if (deg[i]==N-2) { s=i; break; }
	for (int i=0;i<N;i++) if (s!=i&&!G[s][i]) { t=i; break; }
	for (int i=0;i<N;i++) if (s!=i&&t!=i&&G[t][i]) mk[i]=1;
	
	for (int i=0;i<N;i++) for (int j=0;j<N;j++) if (G[i][j]&&i!=j&&mk[i]&&mk[j]) Deg[i]++,vec[i].push_back(j);
	for (int i=0;i<N;i++) if (Deg[i]==1) { DFS(i,-1); break; }
	if (deg[V[0]]<deg[V.back()]) reverse(V.begin(),V.end());
	
	for (int i=0;i<N;i++) if (i!=s&&i!=t&&!mk[i]) {
		H[i]=1;
		for (int j=0;j<V.size();j++) if (G[i][V[j]]) id[i]|=1<<j;
	}
	for (int i=0;i<N;i++) if (H[i]) for (int j=i+1;j<N;j++) if (H[j]&&G[i][j]) add(id[i],id[j]);
	InitMap(n,(int)ans.size());
	for (auto [x,y] : ans) MakeMap(x,y);
	

}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i=0;i<ans.size();i++) MakeG(i,ans[i].first,ans[i].second);
      |               ~^~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int j=0;j<V.size();j++) if (G[i][V[j]]) id[i]|=1<<j;
      |                ~^~~~~~~~~
Bob.cpp:44:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |  for (auto [x,y] : ans) MakeMap(x,y);
      |            ^

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