Submission #1046640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046640		Andrey	Airline Route Map (JOI18_airline)	C++14	85 / 100	320 ms	39364 KiB

Alice

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

void Alice( int n, int m, int a[], int b[] ){
	vector<pair<int,int>> ans(0);
	for(int i = 0; i < m; i++) {
		ans.push_back({a[i],b[i]});
	}
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < n; j++) {
			if((j+1)&(1 << i)) {
				ans.push_back({j,n+i});
			}
		}
	}
	for(int i = 0; i < 9; i++) {
		ans.push_back({n+i,n+10});
		ans.push_back({n+i,n+i+1});
	}
	ans.push_back({n+9,n+11});
	ans.push_back({n+10,n+12});
	ans.push_back({n+11,n+12});
	ans.push_back({n+12,n+13});
	for(int i = 0; i < n+13; i++) {
		ans.push_back({i,n+14});
	}
	InitG(n+15,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;

vector<int> haha[2000];
vector<bool> yeah(2000);
vector<int> wut(0);

void dfs(int a, int t) {
	wut.push_back(a);
	for(int v: haha[a]) {
		if(v != t && yeah[v]) {
			dfs(v,a);
		}
	}
}

void Bob( int v, int u, int c[], int d[] ){
	vector<int> br(v);
	for(int i = 0; i < u; i++) {
		br[c[i]]++;
		br[d[i]]++;
		haha[c[i]].push_back(d[i]);
		haha[d[i]].push_back(c[i]);
	}
	vector<bool> bruh(v,true);
	int p;
	for(int i = 0; i < v; i++) {
		if(br[i] == v-2 || br[i] == 1) {
			bruh[i] = false;
		}
		if(br[i] == 1) {
			p = i;
		}
	}
	bruh[p] = false;
	p = haha[p][0];
	bruh[p] = false;
	int p1,p2;
	for(int v: haha[p]) {
		if(br[v] == 3) {
			p1 = v;
		}
		else if(br[v] == 11) {
			p2 = v;
		}
	}
	bruh[p1] = false;
	bruh[p2] = false;
	int x;
	for(int v: haha[p1]) {
		if(bruh[v]) {
			x = v;
			yeah[v] = true;
		}
	}
	for(int v: haha[p2]) {
		if(bruh[v]) {
			yeah[v] = true;
		}
	}
	dfs(x,-1);
	vector<int> wow(v,-1);
	for(int i = 0; i < wut.size(); i++) {
		bruh[wut[i]] = false;
	}
	for(int i = 0; i < wut.size(); i++) {
		for(int y: haha[wut[i]]) {
			if(bruh[y]) {
				wow[y]+=(1 << (9-i));
			}
		}
	}
	vector<pair<int,int>> ans(0);
	for(int i = 0; i < u; i++) {
		if(bruh[c[i]] && bruh[d[i]]) {
			ans.push_back({wow[c[i]],wow[d[i]]});
		}
	}
	InitMap(v-15,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:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < wut.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Bob.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < wut.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Bob.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Bob.cpp:62:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  dfs(x,-1);
      |  ~~~^~~~~~
Bob.cpp:49:9: warning: 'p2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |  bruh[p2] = false;
      |         ^
Bob.cpp:48:9: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |  bruh[p1] = false;
      |         ^

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