Submission #678198

#	Time	Username	Problem	Language	Result	Execution time	Memory
678198		US3RN4M3	Flights (JOI22_flights)	C++17	0 / 100	12 ms	1736 KiB

Ali

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

namespace {

string str;
string tobstr(int i) {
	string ret(15, '0');
	for(int b = 0; b < 15; b++) {
		if(i & (1 << b)) ret[b] = '1';
	}
	return ret;
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
	vector<vector<int>> graph(N);
	for(int i = 0; i < N - 1; i++) {
		graph[U[i]].push_back(V[i]);
		graph[V[i]].push_back(U[i]);
	}
	int root;
	for(int i = 0; i < N; i++) {
		if(graph[i].size() <= 2) {
			root = i;
			break;
		}
	}
	vector<pair<int, int>> chld; 
	function<void(int, int)> dfs = [&](int cur, int pre) {
		vector<int> nxts;
		for(int nxt : graph[cur]) if(nxt != pre) {
			nxts.push_back(nxt);
		}
		int my_pos = chld.size();
		SetID(cur, my_pos);
		chld.push_back({0, 0});
		if(nxts.size() == 0) return;
		int l_pos = chld.size();
		chld[my_pos].first = l_pos;
		dfs(nxts[0], cur);
		if(nxts.size() == 1) return;
		int r_pos = chld.size();
		chld[my_pos].second = r_pos;
		dfs(nxts[1], cur);
	};
	dfs(root, -1);
	str.clear();
	for(int i = 0; i < N; i++) {
		str += tobstr(chld[i].first);
		str += tobstr(chld[i].second);
	}
}

std::string SendA(std::string S) {
	return str;
}

Benjamin

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

namespace {
int x, y, n;
int frbstr(string s) {
	int ret = 0;
	for(int b = 0; b < 15; b++) {
		if(s[b] == '1') ret += (1 << b);
	}
	return ret;
}
}

std::string SendB(int N, int X, int Y) {
	x = X;
	y = Y;
	n = N;
	return string(20, '0');
}

int Answer(std::string T) {
	vector<pair<int, int>> chld(n);
	for(int i = 0; i < n; i++) {
		chld[i].first = frbstr(T.substr(30*i, 15));
		chld[i].second = frbstr(T.substr(30*i + 15, 15));
	}
	vector<vector<int>> graph(n);
	for(int i = 0; i < n; i++) {
		if(chld[i].first) {
			graph[i].push_back(chld[i].first);
			graph[chld[i].first].push_back(i);
		}
		if(chld[i].second) {
			graph[i].push_back(chld[i].second);
			graph[chld[i].second].push_back(i);
		}
	}
	vector<int> dist(n, 0);
	vector<int> vis(n, false);
	vis[x] = true;
	dist[x] = 0;
	vector<int> q{x};
	int qidx = 0;
	while(qidx < q.size()) {
		int cur = q[qidx++];
		for(int nxt : graph[cur]) {
			if(vis[nxt]) continue;
			vis[nxt] = true;
			dist[nxt] = dist[cur] + 1;
			q.push_back(nxt);
		}
	}
	return dist[y];
}

Compilation message (stderr)

Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:22:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |  int root;
      |      ^~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'int Answer(std::string)':
Benjamin.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  while(qidx < q.size()) {
      |        ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85