Submission #935993

#	Time	Username	Problem	Language	Result	Execution time	Memory
935993		velislavgarkov	Airline Route Map (JOI18_airline)	C++14	0 / 100	372 ms	40204 KiB

Alice

#include "Alicelib.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
using namespace std;
const int MAXN=1e3+24;
int n, m;
vector <pair <int,int> > edges;
void Alice( int N, int M, int A[], int B[] ){
	n=N;
	m=M;
	for (int i=0;i<=9;i++) {
		for (int j=0;j<n;j++) {
			if ((j & (1<<i))) {
				edges.push_back({n+i,j});
			}
		}
	}
	for (int i=0;i<n+10;i++) edges.push_back({i,n+11});
	for (int i=0;i<=9;i++) {
		if (i>0) edges.push_back({n+i-1,n+i});
		edges.push_back({n+10,n+i});
	}
	for (int i=0;i<m;i++) edges.push_back({A[i],B[i]});
	InitG(n+12,edges.size());
	for (int i=0;i<edges.size();i++) MakeG(i,edges[i].first,edges[i].second);
}

Bob

#include "Boblib.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
const int MXN=1e3+10;
using namespace std;
vector <int> v[MXN], line, st;
vector <pair <int, int> > ans;
bool used[MXN], notn[MXN], bin[MXN], in_line[MXN];
int num[MXN], start, zero;
void find_line(int x) {
	line.push_back(x);
	in_line[x]=true;
	for (auto i:v[x]) {
		if (in_line[i] || !bin[i]) continue;
		find_line(i);
	}
}
void Bob( int V, int U, int C[], int D[] ){
	cout << V << endl;
	for (int i=0;i<U;i++) {
		v[C[i]].push_back(D[i]);
		v[D[i]].push_back(C[i]);
	}
	start=-1;
	for (int i=0;i<V;i++) {
		if (v[i].size()==V-2) {
			notn[i]=true;
			used[i]=true;
			in_line[i]=true;
			for (auto j:v[i]) used[j]=true;
			for (int j=0;j<V;j++) {
				if (!used[j]) {
					start=j;
					break;
				}
			}
			break;
		}
	}
	if (start==-1) return;
	notn[start]=true;
	in_line[start]=true;
	for (auto i:v[start]) {
		st.push_back(i);
		bin[i]=true;
		notn[i]=true;
	}
	zero=-1;
	for (auto i:st) {
		int cnt=0;
		for (auto j:v[i]) {
			if (bin[j]) cnt++;
		}
		if (cnt==1) {
			if (zero==-1) zero=i;
			else if (v[zero].size()<v[i].size()) zero=i;
		}
	}
	if (zero==-1) return;
	find_line(zero);
	for (int i=0;i<line.size();i++) {
		for (auto j:v[line[i]]) {
			if (notn[j]) continue;
			num[j]+=(1<<i);
		}
	}
	for (int i=0;i<V;i++) {
		if (notn[i]) continue;
		for (auto j:v[i]) {
			if (notn[j]) continue;
			if (num[i]<num[j]) ans.push_back({num[i],num[j]});
		}
	}
	InitMap(V-12,ans.size());
	for (int i=0;i<ans.size();i++) MakeMap(ans[i].first,ans[i].second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:27: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]
   27 |  for (int i=0;i<edges.size();i++) MakeG(i,edges[i].first,edges[i].second);
      |               ~^~~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if (v[i].size()==V-2) {
      |       ~~~~~~~~~~~^~~~~
Bob.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i=0;i<line.size();i++) {
      |               ~^~~~~~~~~~~~
Bob.cpp:77: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]
   77 |  for (int i=0;i<ans.size();i++) MakeMap(ans[i].first,ans[i].second);
      |               ~^~~~~~~~~~~

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