Submission #1206620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206620		PenguinsAreCute	Flights (JOI22_flights)	C++20	48 / 100	151 ms	2024 KiB

Ali

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

namespace {
	vector<vector<int>> adj;
	string toBin(int n, int l) {
		string s(l, '0');
		for(int i=0;i<l;i++)
			s[i] = !!(n & (1 << i)) + '0';
		return s;
	}
	int toDec(string s) {
		reverse(s.begin(),s.end());
		int ans = 0;
		for(auto i: s)
			ans = (ans << 1) | (i & 1);
		return ans;
	}
	int euler[20'005], dist[10'005], n;
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	n = N;
	adj.clear();
	adj.resize(N);
	for(int i=0;i<N-1;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	auto dfs = [&adj,cnt=0](auto &self, int x, int p) mutable -> void {
		SetID(x, cnt);
		euler[cnt++] = x;
		for(auto i: adj[x])
			if(i != p) {
				self(self, i, x);
				euler[cnt++] = x;
			}
	};
	dfs(dfs, 0, -1);
}

std::string SendA(std::string S) {
	int M = toDec(S);
	int x = M / 100 * 2;
	int k = (M % 100) * 200;
	auto dfs = [&adj](auto &self, int x, int p) mutable -> void {
		for(auto i: adj[x])
			if(i != p) {
				dist[i] = dist[x] + 1;
				self(self, i, x);
			}
	};

	dist[euler[x+1]] = 0;
	dfs(dfs, euler[x+1], -1);
	int dst = dist[euler[k]];
	dist[euler[x]] = 0;
	dfs(dfs, euler[x], -1);

	string ret;
	for(int i=0;i<2*n-2;i++)
		if(euler[i] == euler[x+1] && euler[i+1] == euler[x])
			ret = toBin(i, 15);
	assert(ret.size() == 15);

	ret += toBin(dist[euler[k]], 14);
	if(dist[euler[k]] < dst)
		ret += '1';
	else
		ret += '0';
	for(int i=0;i<min(199,2*n-2-k);i++)
		ret += (dist[euler[k+i+1]]>dist[euler[k+i]]?'1':'0');
	return ret;
}

Benjamin

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

namespace {
	string toBin(int n, int l) {
		string s(l, '0');
		for(int i=0;i<l;i++)
			s[i] = !!(n & (1 << i)) + '0';
		return s;
	}
	int toDec(string s) {
		reverse(s.begin(),s.end());
		int ans = 0;
		for(auto i: s)
			ans = (ans << 1) | (i & 1);
		return ans;
	}
	int x, y;
}

std::string SendB(int N, int X, int Y) {
	x = X, y = Y;
	return toBin(100 * (X / 2) + (Y / 200), 20);
}

int Answer(std::string T) {
	int bad = toDec(T.substr(0,15));
	int ans = toDec(T.substr(15,14)) + (x&1?(T[29]&1?1:-1):0);
	for(int i=0;i<(y%200);i++) {
		if((x & 1) && (y - (y % 200) + i == x - 1 || y - (y % 200) + i == bad))
			ans += ((T[i+30]&1)?-1:1);
		else
			ans += ((T[i+30]&1)?1:-1);
	}
	return ans;
}

Compilation message (stderr)

# 1번째 컴파일 단계

Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:31:22: warning: capture of variable '{anonymous}::adj' with non-automatic storage duration
   31 |         auto dfs = [&adj,cnt=0](auto &self, int x, int p) mutable -> void {
      |                      ^~~
Ali.cpp:6:29: note: 'std::vector<std::vector<int> > {anonymous}::adj' declared here
    6 |         vector<vector<int>> adj;
      |                             ^~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:47:22: warning: capture of variable '{anonymous}::adj' with non-automatic storage duration
   47 |         auto dfs = [&adj](auto &self, int x, int p) mutable -> void {
      |                      ^~~
Ali.cpp:6:29: note: 'std::vector<std::vector<int> > {anonymous}::adj' declared here
    6 |         vector<vector<int>> adj;
      |                             ^~~

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