Submission #783832

#	Time	Username	Problem	Language	Result	Execution time	Memory
783832		PoonYaPat	Airline Route Map (JOI18_airline)	C++14	100 / 100	622 ms	29336 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

void Alice( int n, int m, int A[], int B[] ){
	vector<pii> v;
	for (int i=0; i<=n+11; ++i) if (i!=n && i!=n+1) v.push_back({n,i});
	for (int i=0; i<n; ++i) v.push_back({n+1,i});
	for (int i=n+3; i<=n+11; ++i) v.push_back({i,i-1});
	for (int i=0; i<n; ++i) {
		for (int j=0; j<10; ++j) {
			if (i&(1<<j)) v.push_back({i,n+2+j});
		}
	}
	for (int i=0; i<m; ++i) v.push_back({A[i],B[i]});
	InitG(n+12,v.size());
	for (int i=0; i<v.size(); ++i) MakeG(i,v[i].first,v[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int st,nx,re[1020];
vector<int> adj[1020];
bool mark[1020];

void dfs(int x, int par, int val) {
	int nxt=-1;
	for (auto s : adj[x]) {
		if (s==par || s==st) continue;
		if (mark[s]) re[s]+=val;
		else nxt=s;
	}
	if (nxt!=-1) dfs(nxt,x,val*2);
}

void Bob(int n, int m, int C[], int D[] ){
	vector<pii> v;
	for (int i=0; i<m; ++i) {
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	for (int i=0; i<n; ++i) {
		if (adj[i].size()==n-2) {
			bool have[1050];
			memset(have,0,sizeof(have));
			have[i]=true;
			for (auto s : adj[i]) have[s]=true;
			for (int j=0; j<n; ++j) if (!have[j] && adj[j].size()==n-12) {
				st=i;
				nx=j;
			}
		}
	}

	for (auto s : adj[nx]) mark[s]=true;
	
	int p=-1;
	for (int i=0; i<n; ++i) if (i!=st && i!=nx && !mark[i]) {
		int cnt=0;
		for (auto s : adj[i]) if (!mark[s]) ++cnt;
		if (cnt==2) {
			if (p==-1) p=i;
			else if (adj[i].size()>adj[p].size()) p=i;
		}
	}
	dfs(p,p,1);

	for (int i=0; i<m; ++i) {
		if (mark[C[i]] && mark[D[i]]) {
			v.push_back({re[C[i]],re[D[i]]});
		}
	}

	InitMap(n-12,v.size());
	for (auto s : v) MakeMap(s.first,s.second);
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:27:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   if (adj[i].size()==n-2) {
      |       ~~~~~~~~~~~~~^~~~~
Bob.cpp:32:57: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |    for (int j=0; j<n; ++j) if (!have[j] && adj[j].size()==n-12) {
      |                                            ~~~~~~~~~~~~~^~~~~~

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