Submission #566197

#	Time	Username	Problem	Language	Result	Execution time	Memory
566197		8e7	Flights (JOI22_flights)	C++17	63 / 100	302 ms	2880 KiB

Ali

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

namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
	const int bs = 10;
	vector<int> adj[maxn];
	int bid[maxn], bord[maxn], siz[maxn], par[maxn], dep[maxn], id[maxn];	
	bool isroot[maxn];
	int root[maxn];
	string trav[maxn];
	int C = 0;
	
	int st;
	void dfs(int n, int pa, int d) {
		par[n] = pa;
		dep[n] = d;
		siz[n] = 1;
		debug(n);
		for (int v:adj[n]) {
			if (v != pa) {
				dfs(v, n, d+1);
				if (siz[v] < bs) {
					siz[n] += siz[v];
				}
			}
		}
		if (siz[n] >= bs || n == st) {
			debug("root", n, siz[n]);
			isroot[n] = 1;
			bid[n] = C;
			root[C++] = n;
		}
	}
	void getb(int n, int pa, int &ti) {
		bord[n] = ti++;
		
		for (int v:adj[n]) {
			if (v != pa && !isroot[v]) {
				trav[bid[n]] += '1';
				bid[v] = bid[n];
				getb(v, n, ti);
				trav[bid[n]] += '0';
			}
		}
	}
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
	for (int i = 0;i < N;i++) {
		adj[i].clear();
		trav[i].clear();
		bid[i] = 0, bord[i] = 0;
		siz[i] = 0;
		isroot[i] = 0, root[i] = 0;
	}
	C = 0;

	for (int i = 0;i < N - 1;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	for (int i = 0;i < N;i++) {
		if (adj[i].size() == 1) {
			st = i;
			dfs(st, -1, 0);
			break;
		}
	}
	
	for (int i = 0;i < N;i++) {
		if (isroot[i]) {
			int tmp = 0;
			getb(i, par[i], tmp);
		}
	}
	for (int i = 0;i < C;i++) {
		while (trav[i].size() < 36) trav[i] += '0';
	}
	for (int i = 0;i < N;i++) {
		id[i] = bid[i] * 2 * bs + bord[i];	
		//debug(bid[i], bord[i]);
		SetID(i, id[i]);
	}
}

std::string SendA(std::string S) {
	int bx = 0, by = 0;
	for (int i = 0;i < 10;i++) bx += (S[i] - '0') * (1<<i);
	for (int i = 10;i < 20;i++) by += (S[i] - '0') * (1<<(i-10));
	debug("senda", bx, by);

	int dis = 0;	
	int px = root[bx], py = root[by], v = 0;
	while (px != py) {
		if (dep[px] < dep[py]) swap(px, py);
		px = par[px];
		dis++;
		if (bid[px] == bid[py] && bid[px] == bx) {
			v = bord[px];	
			break;
		}
	}
	debug(dis);

	string ret;
	for (int i = 0;i < 14;i++) ret += char(((dis >> i) & 1) + '0'); 
	ret.insert(ret.end(), trav[bx].begin(), trav[bx].end());
	ret.insert(ret.end(), trav[by].begin(), trav[by].end());
	for (int i = 0;i < 5;i++) ret += char(((v >> i) & 1) + '0');	
	debug(ret);
	return ret;
}

Benjamin

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

#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
	void debug(){cout << endl;}
	template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
	template<class T> void pary(T l, T r) {
		while (l != r) cout << *l << " ", l++;
		cout << endl;
	}
#else
#define debug(...) 0
#define pary(...) 0
#endif
	const int bs = 10;
	int bx, by, dx, dy;
	int par[maxn], dep[maxn];
	void decode(string s) {
		int d = 0, cur = 0, id = 0;
		dep[cur] = 0;
		for (auto i:s) {
			d += (i == '1' ? 1 : -1);
			if (i - '0') {
				dep[++id] = d;
				par[id] = cur;
				cur = id;
			} else {
				if (d < 0) return;
				cur = par[cur];
			}
		}
	}
}

std::string SendB(int N, int X, int Y) {
	bx = X / (2 * bs), by = Y / (2 * bs);	
	dx = X % (2 * bs), dy = Y % (2 * bs);
	if (bx < by) swap(bx, by), swap(dx, dy);
	string ret;
	for (int i = 0;i < 10;i++) ret += char(((bx >> i) & 1) + '0');
	for (int i = 0;i < 10;i++) ret += char(((by >> i) & 1) + '0');
	debug(bx, dx, by, dy);
	return ret;
}

int Answer(std::string T) {
	int ret = 0;
	for (int i = 0;i < 14;i++) {
		ret += (1<<i) * (T[i] - '0');
	}
	if (bx != by) {
		decode(T.substr(14, 36));	
		int v = 0;	
		for (int i = 0;i < 5;i++) v += (1<<i) * (T[86 + i] - '0');
		if (v) {
			while (dx != v) {
				if (dep[dx] < dep[v]) swap(dx, v);
				dx = par[dx];
				ret++;
			}
		} else {
			ret += dep[dx];
		}

		decode(T.substr(50, 36));
		ret += dep[dy];	
	} else {
		decode(T.substr(14, 36));
		while (dx != dy) {
			if (dep[dx] < dep[dy]) swap(dx, dy);
			dx = par[dx];
			ret++;
		}
	}
	return ret;
}

Compilation message (stderr)

Ali.cpp: In function 'void {anonymous}::dfs(int, int, int)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:36:3: note: in expansion of macro 'debug'
   36 |   debug(n);
      |   ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:46:4: note: in expansion of macro 'debug'
   46 |    debug("root", n, siz[n]);
      |    ^~~~~
Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:108:2: note: in expansion of macro 'debug'
  108 |  debug("senda", bx, by);
      |  ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:121:2: note: in expansion of macro 'debug'
  121 |  debug(dis);
      |  ^~~~~
Ali.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
Ali.cpp:128:2: note: in expansion of macro 'debug'
  128 |  debug(ret);
      |  ^~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'std::string SendB(int, int, int)':
Benjamin.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 0
      |                    ^
Benjamin.cpp:50:2: note: in expansion of macro 'debug'
   50 |  debug(bx, dx, by, dy);
      |  ^~~~~

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