Submission #544502

#	Time	Username	Problem	Language	Result	Execution time	Memory
544502		model_code	Flights (JOI22_flights)	C++17	95 / 100	2083 ms	6944 KiB

Ali

#include "Ali.h"
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

namespace {
	
	const int LIMIT1 = 7;
	const int LIMIT2 = 13;
	const int BACKET = 4;
	const int TREEWAY = 66;
	
	// Memo
	int Scenario = 0;
	int MainRoot = 0;
	int Cnt = 0, Rank;
	int cl[20029], CntP;
	int ID[20029];
	vector<int> tmp;
	string str_tmp = "";
	
	// Graph
	int N, U[20029], V[20029];
	int dist[20029];
	int Par[20029];
	vector<int> G[20029];
	vector<int> Gc[20029];
	
	// Group Division
	int groupcnt = 0;
	int group[20029];      // Group ID
	int groupnum[20029];   // Vertex ID in group
	int dp[20029];
	vector<int> S[20029];  // Connect or Cut
	vector<int> Gr[20029]; // Group Division
	
	// Tree Parentheses
	map<string, int> Map;
	vector<string> Tree;
	
	void AllInit() {
		Cnt = 0; Rank = 0;
		groupcnt = 0; MainRoot = -1; str_tmp = "";
		tmp.clear();
		for (int i = 0; i < 20029; i++) {
			cl[i] = 0; ID[i] = 0;
			U[i] = 0; V[i] = 0; G[i].clear();
			dist[i] = 0; Par[i] = 0;
			group[i] = 0; groupnum[i] = 0; dp[i] = 0;
			S[i].clear(); Gr[i].clear();
		}
	}
	
	pair<string, bool> dfs_check(int pos) {
		vector<string> Vlist;
		string Vreturn = "0";
		bool CurrentState = true;
		dp[pos] = 1;
		for (int to : Gc[pos]) {
			pair<string, bool> ret = dfs_check(to);
			Vlist.push_back(ret.first);
			Vreturn += ret.first;
			dp[pos] += dp[to];
			if (ret.second == false) CurrentState = false;
		}
		for (int i = 0; i < (int)Vlist.size() - 1; i++) {
			if (Vlist[i] > Vlist[i + 1]) CurrentState = false;
		}
		Vreturn += "1";
		return make_pair(Vreturn, CurrentState);
	}
	
	bool hantei(string ss) {
		for (int i = 0; i < (int)ss.size() / 2 + 1; i++) Gc[i].clear();
		for (int i = 0; i < (int)ss.size() / 2 + 1; i++) dp[i] = 0;
		stack<int> ST;
		int num = 1; ST.push(0);
		for (int i = 0; i < (int)ss.size(); i++) {
			if (ss[i] == '0') {
				int u1 = ST.top(), u2 = num;
				ST.push(u2);
				Gc[u1].push_back(u2);
				num += 1;
			}
			if (ss[i] == '1') {
				ST.pop();
			}
		}
		
		// Subtree Size Check
		pair<string, bool> u = dfs_check(0);
		for (int i = 1; i < num; i++) {
			if (dp[i] >= 7) return false;
		}
		for (int i = 0; i < num; i++) {
			if (Gc[i].size() >= 3) return false;
		}
		if (u.second == false) return false;
		return true;
	}
	
	void dfs_init(int pos, int dep, string ss) {
		if (dep == 0 && pos == (LIMIT2 - 1) * 2 && hantei(ss) == true) {
			int idx = Tree.size();
			Map[ss] = idx;
			Tree.push_back(ss);
		}
		if (pos >= (LIMIT2 - 1) * 2 || dep > (LIMIT2 - 1) * 2 - pos) {
			return;
		}
		string s1 = ss + "0";
		string s2 = ss + "1";
		dfs_init(pos + 1, dep + 1, s1);
		if (dep >= 1) dfs_init(pos + 1, dep - 1, s2);
	}
	
	void init() {
		dfs_init(0, 0, "");
	}
};

int ToNumber(string ss) {
	int cur = 0;
	for (int i = 0; i < (int)ss.size(); i++) {
		if (ss[i] == '1') cur += (1 << i);
	}
	return cur;
}

string ToString(long long val, int len) {
	string ss = "";
	for (int i = 0; i < len; i++) {
		if ((val & (1LL << i)) == 0) ss += "0";
		if ((val & (1LL << i)) != 0) ss += "1";
	}
	return ss;
}

void dfs1(int pos, int par) {
	dp[pos] = 1;
	Par[pos] = par;
	for (int to : G[pos]) {
		if (to == par) continue;
		dfs1(to, pos);
		if (dp[to] < LIMIT1) {
			S[pos].push_back(to);
			S[to].push_back(pos);
			dp[pos] += dp[to];
		}
		else {
			tmp.push_back(to);
		}
	}
}

string dfs2_1(int pos, int par) {
	vector<pair<string, int>> Vlist;
	for (int to : S[pos]) {
		if (to == par) continue;
		string u = dfs2_1(to, pos);
		Vlist.push_back(make_pair(u, to));
	}
	
	// Rearrange S[pos]
	sort(Vlist.begin(), Vlist.end());
	S[pos].clear();
	string Vreturn = "0";
	for (int i = 0; i < (int)Vlist.size(); i++) {
		S[pos].push_back(Vlist[i].second);
		Vreturn += Vlist[i].first;
	}
	if (par != -1) S[pos].push_back(par);
	
	// Return
	Vreturn += "1";
	return Vreturn;
}

void dfs2_2(int pos, int par) {
	group[pos] = groupcnt;
	groupnum[pos] = (int)Gr[groupcnt].size();
	Gr[groupcnt].push_back(pos);
	
	// Recursion
	for (int to : S[pos]) {
		if (to == par) continue;
		dfs2_2(to, pos);
	}
}

void dfs3(int pos, int dep) {
	dist[pos] = dep;
	for (int to : G[pos]) {
		if (dist[to] != -1) continue;
		dfs3(to, dep + 1);
	}
}

void dfs5(int pos, int par) {
	cl[pos] = CntP;
	CntP += 1;
	for (int to : S[pos]) {
		if (to == par) continue;
		str_tmp += "0";
		dfs5(to, pos);
		str_tmp += "1";
	}
}

void Init(int n, vector<int> u, vector<int> v) {
	AllInit();
	if (Scenario == 0) init();
	Scenario += 1;
	
	// Initialize
	N = n;
	for (int i = 0; i < N - 1; i++) {
		U[i] = u[i];
		V[i] = v[i];
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	
	// Get Root
	for (int i = 0; i < N; i++) {
		if (G[i].size() == 1) { MainRoot = i; break; }
	}
	
	// Group Division [Part 1]
	for (int i = 0; i < N; i++) dp[i] = 0;
	tmp.push_back(MainRoot);
	dfs1(MainRoot, -1);
	
	// Add Vertices to 13
	int NumVertices = N;
	for (int root : tmp) {
		for (int seco : S[root]) {
			int cx = seco, par = root;
			while (true) {
				int nex = -1;
				for (int to : S[cx]) { if (to != par) nex = to; }
				if (nex == -1) break;
				par = cx; cx = nex;
			}
			int Last = cx;
			for (int k = 0; k < 6 - dp[seco]; k++) {
				S[Last].push_back(NumVertices);
				S[NumVertices].push_back(Last);
				G[Last].push_back(NumVertices);
				G[NumVertices].push_back(Last);
				//cout << "root = " << root << ", Edge = (" << Last << ", " << NumVertices << ")" << endl;
				Last = NumVertices;
				NumVertices += 1;
			}
		}
		for (int j = 0; j < 2 - (int)S[root].size(); j++) {
			int Last = root;
			for (int k = 0; k < 6; k++) {
				S[Last].push_back(NumVertices);
				S[NumVertices].push_back(Last);
				G[Last].push_back(NumVertices);
				G[NumVertices].push_back(Last);
				//cout << "root = " << root << ", Edge = (" << Last << ", " << NumVertices << ")" << endl;
				Last = NumVertices;
				NumVertices += 1;
			}
		}
	}
	
	// Get Distance
	for (int i = 0; i < NumVertices; i++) dist[i] = -1;
	dfs3(MainRoot, 0);
	vector<pair<int, int>> DistSort;
	for (int i = 0; i < NumVertices; i++) DistSort.push_back(make_pair(dist[i], i));
	sort(DistSort.begin(), DistSort.end());
	
	// Group Division [Part 2]
	for (int i = 0; i < NumVertices; i++) group[i] = -1;
	for (int i = 0; i < NumVertices; i++) {
		int idx = DistSort[i].second;
		if (group[idx] != -1) continue;
		dfs2_1(idx, -1);
		dfs2_2(idx, -1);
		groupcnt += 1;
	}
	
	// Set ID
	for (int i = 0; i < groupcnt; i++) {
		CntP = 0;
		dfs5(Gr[i][0], -1);
		for (int j = 0; j < (int)Gr[i].size(); j++) {
			if (Gr[i][j] >= N) continue;
			ID[Gr[i][j]] = LIMIT2 * i + cl[Gr[i][j]];
			SetID(Gr[i][j], ID[Gr[i][j]]);
		}
	}
}

string SendA(string S) {
	// Get Group Number
	int GX = 0, GY = 0;
	Rank = ToNumber(S);
	for (int i = 0; i < 1430; i++) {
		for (int j = i; j < 1430; j++) {
			if (Cnt == Rank) { GX = i; GY = j; }
			Cnt += 1;
		}
	}
	
	// Get String When GX == GY
	if (GX == GY) {
		str_tmp = "";
		dfs5(Gr[GX][0], -1);
		int num_Tree = Map[str_tmp];
		return ToString(num_Tree, 10);
	}
	
	// Get String When GX != GY
	if (GX != GY) {
		string str = "";
		
		// Get GX-GY Path
		int pos = Gr[GY][0];
		while (pos != -1 && group[pos] != GX) {
			pos = Par[pos];
		}
		
		// Get "Representative" Vertex in Group
		int u1 = Gr[GX][0]; if (pos != -1) u1 = pos;
		int u2 = Gr[GY][0];
		
		// Send Tree of GX
		str_tmp = "";
		dfs5(Gr[GX][0], -1);
		long long num_GX = Map[str_tmp]; //cout << str_tmp << " " << Map[str_tmp] << endl;
		
		// Send Tree of GY
		str_tmp = "";
		dfs5(Gr[GY][0], -1);
		long long num_GY = Map[str_tmp];
		long long rep_GX = ID[u1] % LIMIT2; //cout << str_tmp << " " << Map[str_tmp] << endl;
		
		// Get Distance between u1 and u2
		for (int i = 0; i < N; i++) dist[i] = -1;
		dfs3(u1, 0);
		long long dst_path = dist[u2];
		
		// Get String & Return
		long long FinalVal = 0;
		FinalVal += 1LL * num_GX;
		FinalVal += 1LL * num_GY * TREEWAY;
		FinalVal += 1LL * rep_GX * TREEWAY * TREEWAY;
		FinalVal += 1LL * dst_path * TREEWAY * TREEWAY * LIMIT2;
		for (int i = 1; i <= 30; i++) {
			if (FinalVal < (1LL << i)) return ToString(FinalVal, i);
			else FinalVal -= (1LL << i);
		}
	}
}

Benjamin

#include "Benjamin.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;

namespace {
	
	const int LIMIT2 = 13;
	const int BACKET = 4;
	const int TREEWAY = 66;
	
	// Group
	int Scenario = 0;
	int N, X, Y;
	int Cnt = 0, Rank;
	int GroupX, NumX;
	int GroupY, NumY;
	
	// Graph
	vector<int> G[20029];
	vector<int> Gc[20029];
	int dist[20029], CntS;
	int dp[20029];
	
	// Tree Parentheses
	map<string, int> Map;
	vector<string> Tree;
	
	void AllInit() {
		Cnt = 0; Rank = 0; CntS = 0;
		for (int i = 0; i < 20029; i++) {
			G[i].clear(); dist[i] = 0;
		}
	}
	
	pair<string, bool> dfs_check(int pos) {
		vector<string> Vlist;
		string Vreturn = "0";
		bool CurrentState = true;
		dp[pos] = 1;
		for (int to : Gc[pos]) {
			pair<string, bool> ret = dfs_check(to);
			Vlist.push_back(ret.first);
			Vreturn += ret.first;
			dp[pos] += dp[to];
			if (ret.second == false) CurrentState = false;
		}
		for (int i = 0; i < (int)Vlist.size() - 1; i++) {
			if (Vlist[i] > Vlist[i + 1]) CurrentState = false;
		}
		Vreturn += "1";
		return make_pair(Vreturn, CurrentState);
	}
	
	bool hantei(string ss) {
		for (int i = 0; i < (int)ss.size() / 2 + 1; i++) Gc[i].clear();
		for (int i = 0; i < (int)ss.size() / 2 + 1; i++) dp[i] = 0;
		stack<int> ST;
		int num = 1; ST.push(0);
		for (int i = 0; i < (int)ss.size(); i++) {
			if (ss[i] == '0') {
				int u1 = ST.top(), u2 = num;
				ST.push(u2);
				Gc[u1].push_back(u2);
				num += 1;
			}
			if (ss[i] == '1') {
				ST.pop();
			}
		}
		
		// Subtree Size Check
		pair<string, bool> u = dfs_check(0);
		for (int i = 1; i < num; i++) {
			if (dp[i] >= 7) return false;
		}
		for (int i = 0; i < num; i++) {
			if (Gc[i].size() >= 3) return false;
		}
		if (u.second == false) return false;
		return true;
	}
	
	void dfs_init(int pos, int dep, string ss) {
		if (dep == 0 && pos == (LIMIT2 - 1) * 2 && hantei(ss) == true) {
			int idx = Tree.size();
			Map[ss] = idx;
			Tree.push_back(ss);
		}
		if (pos >= (LIMIT2 - 1) * 2 || dep > (LIMIT2 - 1) * 2 - pos) {
			return;
		}
		string s1 = ss + "0";
		string s2 = ss + "1";
		dfs_init(pos + 1, dep + 1, s1);
		if (dep >= 1) dfs_init(pos + 1, dep - 1, s2);
	}
	
	void init() {
		dfs_init(0, 0, "");
	}
};

long long ToNumber2(string ss) {
	long long cur = 0;
	for (int i = 0; i < (int)ss.size(); i++) {
		if (ss[i] == '1') cur += (1LL << i);
	}
	return cur;
}

string ToString2(int val, int len) {
	string ss = "";
	for (int i = 0; i < len; i++) {
		if ((val & (1 << i)) == 0) ss += "0";
		if ((val & (1 << i)) != 0) ss += "1";
	}
	return ss;
}

void MakeGraph(string V) {
	stack<int> Stack;
	for (int i = 0; i < (int)V.size(); i++) G[i].clear();
	CntS = 1; Stack.push(0);
	for (int i = 0; i < (int)V.size(); i++) {
		if (V[i] == '0') {
			int u1 = Stack.top(), u2 = CntS;
			CntS += 1;
			Stack.push(u2);
			G[u1].push_back(u2);
			G[u2].push_back(u1);
		}
		else {
			if (Stack.size() == 0) break;
			Stack.pop();
		}
	}
}

void dfs4(int pos, int dep) {
	dist[pos] = dep;
	for (int to : G[pos]) {
		if (dist[to] != -1) continue;
		dfs4(to, dep + 1);
	}
}

int GetDist(int u1, int u2) {
	for (int i = 0; i < 20020; i++) dist[i] = -1;
	dfs4(u1, 0);
	return dist[u2];
}

string SendB(int n, int x, int y) {
	AllInit();
	if (Scenario == 0) init();
	Scenario += 1;
	
	N = n; X = x; Y = y;
	if (X > Y) swap(X, Y);
	GroupX = X / LIMIT2; NumX = X % LIMIT2;
	GroupY = Y / LIMIT2; NumY = Y % LIMIT2;
	
	// Get Rank
	for (int i = 0; i < 1430; i++) {
		for (int j = i; j < 1430; j++) {
			if (i == GroupX && j == GroupY) Rank = Cnt;
			Cnt += 1;
		}
	}
	
	// Send Email
	return ToString2(Rank, 20);
}

int Answer(string T) {
	// If the group is same
	if (GroupX == GroupY) {
		string Tree1 = Tree[ToNumber2(T)];
		MakeGraph(Tree1);
		return GetDist(NumX, NumY);
	}
	
	// If the group is not same
	if (GroupX != GroupY) {
		long long RecieveVal = ToNumber2(T);
		for (int i = 1; i < T.size(); i++) RecieveVal += (1LL << i);
		int TreeV1 = RecieveVal % TREEWAY;
		int TreeV2 = (RecieveVal / (TREEWAY)) % TREEWAY;
		int VertX = (RecieveVal / (TREEWAY * TREEWAY)) % LIMIT2;
		int d3 = (RecieveVal / (TREEWAY * TREEWAY * LIMIT2));
		
		// Get d1, d2
		int d1 = 0, d2 = 0;
		string Tree1 = Tree[TreeV1];
		string Tree2 = Tree[TreeV2];
		MakeGraph(Tree1); d1 = GetDist(VertX, NumX);
		MakeGraph(Tree2); d2 = GetDist(0, NumY);
		
		// Return
		return d1 + d2 + d3;
	}
}

Compilation message (stderr)

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:363:1: warning: control reaches end of non-void function [-Wreturn-type]
  363 | }
      | ^
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:191:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   for (int i = 1; i < T.size(); i++) RecieveVal += (1LL << i);
      |                   ~~^~~~~~~~~~
Benjamin.cpp:207:1: warning: control reaches end of non-void function [-Wreturn-type]
  207 | }
      | ^

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