oj.uz

답안 #544503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544503 2022-04-02T07:03:09 Z model_code Flights (JOI22_flights) C++17
100 / 100
 763 ms 6344 KB 
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	
	// Variables
	const int LIMIT1 = 7;
	const int LIMIT2 = 13;
	int Scenario = 0;
	int N;
	int NumVertices;
	int U[20029], V[20029];
	
	// Tree Division & Distance
	int dp[20029], ord[20029]; string dp2[20029];
	int dist[20029], dia1[20029], dia2[20029];
	vector<int> G[20029];
	
	// Grouping
	int Group[20029], GroupID[20029];
	int GroupTree[20029];
	vector<int> S[20029];
	vector<int> Root;
	vector<int> tmp_DFSord;
	
	// List of Tree
	map<string, int> Map;
	string Tree[400]; int Treecnt = 0;
	vector<int> Treeord[400];
	vector<int> Treeds1[400]; int TreeID1[400];
	vector<int> Treeds2[400][15]; int TreeID2[400][15];
	vector<vector<int>> TreeList1, TreeList2;
	
	// List of Small Trees
	vector<string> TreeList7 = {
		"000011100111", // [0]
		"000011011011", // [1]
		"000001101111", // [2]
		"000110110011", // [3]
		"000011011101"  // [4]
	};
	vector<string> TreeList6 = {
		"0001100111",  // Group 0
		"0001011011",  // Group 1
		"0000111011",  // Group 1
		"0000011111",  // Group 2
		"0000101111",  // Group 2
		"0001101101",  // Group 3
		"0010110011",  // Group 3
		"0001110011",  // Group 3
		"0000110111",  // Group 4
		"0000111101",  // Group 4
		"0001011101"   // Group 4
	};
	
	void AllInit() {
		Root.clear(); NumVertices = 0;
		for (int i = 0; i < 20029; i++) {
			U[i] = 0; V[i] = 0;
			dp[i] = 0; ord[i] = 0; dist[i] = 0; G[i].clear();
			Group[i] = 0; GroupID[i] = 0; GroupTree[i] = 0; S[i].clear();
		}
	}
	
	void MakeGraph(int Vertices, string ss) {
		for (int i = 0; i < Vertices; i++) G[i].clear();
		int num = 1; stack<int> S; S.push(0);
		for (int i = 0; i < (int)ss.size(); i++) {
			if (ss[i] == '0') {
				G[S.top()].push_back(num);
				G[num].push_back(S.top());
				S.push(num); num += 1;
			}
			if (ss[i] == '1') S.pop();
		}
	}
	
	void Get_DP(int pos, int par) {
		dp[pos] = 1;
		dp2[pos] = "";
		for (int to : G[pos]) {
			if (to == par) continue;
			Get_DP(to, pos);
			dp2[pos] += ("0" + dp2[to] + "1");
			dp[pos] += dp[to];
		}
	}
	
	void MakeDist1(int Vertices, int stt) {
		for (int i = 0; i < Vertices; i++) dist[i] = -1;
		queue<int> Q; Q.push(stt); dist[stt] = 0;
		int ordcnt = 0;
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			ord[pos] = ordcnt; ordcnt += 1;
			for (int to : G[pos]) {
				if (dist[to] != -1) continue;
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
	
	void MakeDist2(int Vertices, int stt) {
		for (int i = 0; i < Vertices; i++) dist[i] = -1;
		queue<int> Q; Q.push(stt); dist[stt] = 0;
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			for (int to : G[pos]) {
				if (dist[to] != -1) continue;
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
	
	void ListUpTree() {
		int Level[11] = {0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
		for (int i = 0; i < 11; i++) {
			for (int j = Level[i]; j < 5; j++) {
				string ss = "";
				ss += "0"; ss += TreeList7[j]; ss += "1";
				ss += "0"; ss += TreeList6[i]; ss += "1";
				
				// EndPoint
				vector<bool> EndPoint(14, false);
				if (j == 1) { EndPoint[3] = true; }
				if (j == 2) { EndPoint[4] = true; }
				if (j == 3) { EndPoint[2] = true; }
				if (j == 4) { EndPoint[1] = true; EndPoint[3] = true; }
				
				// Make Graph
				MakeGraph(14, ss);
				Map[ss] = Treecnt;
				Tree[Treecnt] = ss;
				
				// Get Distance
				MakeDist1(14, 0);
				Treeds1[Treecnt] = vector<int>(14, 0);
				for (int i = 0; i < 14; i++) Treeds1[Treecnt][ord[i]] = dist[i];
				for (int i = 0; i < 14; i++) {
					if (G[i].size() == 3 && EndPoint[i] == false) {
						Treeds2[Treecnt][ord[i]] = vector<int>(14, -1);
					}
					else {
						MakeDist2(14, i);
						Treeds2[Treecnt][ord[i]] = vector<int>(14, 0);
						for (int j = 0; j < 14; j++) Treeds2[Treecnt][ord[i]][ord[j]] = dist[j];
					}
				}
				
				// Record Tree (ord, Treecnt++)
				Treeord[Treecnt] = vector<int>(14, 0);
				for (int i = 0; i < 14; i++) Treeord[Treecnt][i] = ord[i];
				Treecnt += 1;
			}
		}
	}
	
	void Initialize() {
		for (int i = 0; i < 400; i++) {
			TreeID1[i] = -1;
			for (int j = 0; j < 15; j++) TreeID2[i][j] = -1;
		}
		ListUpTree();
		for (int i = 0; i < Treecnt; i++) {
			int Verts = Tree[i].size() / 2 + 1;
			TreeList1.push_back(Treeds1[i]);
			for (int j = 0; j < Verts; j++) {
				if (Treeds2[i][j][0] != -1) TreeList2.push_back(Treeds2[i][j]);
			}
		}
		sort(TreeList1.begin(), TreeList1.end()); TreeList1.erase(unique(TreeList1.begin(), TreeList1.end()), TreeList1.end());
		sort(TreeList2.begin(), TreeList2.end()); TreeList2.erase(unique(TreeList2.begin(), TreeList2.end()), TreeList2.end());
		for (int i = 0; i < Treecnt; i++) {
			int Verts = Tree[i].size() / 2 + 1;
			TreeID1[i] = lower_bound(TreeList1.begin(), TreeList1.end(), Treeds1[i]) - TreeList1.begin();
			for (int j = 0; j < Verts; j++) {
				if (Treeds2[i][j][0] == -1) TreeID2[i][j] = -1;
				else TreeID2[i][j] = lower_bound(TreeList2.begin(), TreeList2.end(), Treeds2[i][j]) - TreeList2.begin();
			}
		}
		//cout << Treecnt << " " << TreeList1.size() << " " << TreeList2.size() << endl;
	}
	
	// Number -> String
	string NumberToString(long long val, int LEN) {
		string str = "";
		for (int i = 0; i < LEN; i++) {
			if ((val & (1LL << i)) == 0) str += "0";
			if ((val & (1LL << i)) != 0) str += "1";
		}
		return str;
	}
	
	// String -> Number
	int StringToNumber(string str, int LEN) {
		long long val = 0;
		for (int i = 0; i < LEN; i++) {
			if (str[i] == '1') val += (1LL << i);
		}
		return val;
	}
	
	// Get Division in Graph G
	void dfs_Division(int pos) {
		dp[pos] = 1;
		for (int to : G[pos]) {
			if (dp[to] != 0) continue;
			dfs_Division(to);
			if (dp[to] >= LIMIT1) Root.push_back(to);
			else {
				dp[pos] += dp[to];
				S[pos].push_back(to);
				S[to].push_back(pos);
			}
		}
	}
	
	// Get String in Graph S
	pair<int, string> dfs_GetString(int pos, int par) {
		vector<tuple<int, string, int>> tmp;
		for (int to : S[pos]) {
			if (to == par) continue;
			pair<int, string> rem = dfs_GetString(to, pos);
			tmp.push_back(make_tuple(rem.first, rem.second, to));
		}
		sort(tmp.begin(), tmp.end());
		reverse(tmp.begin(), tmp.end());
		string str = ""; int dp_tmp = 1;
		for (int i = 0; i < (int)tmp.size(); i++) {
			str += ("0" + get<1>(tmp[i]) + "1");
			dp_tmp += get<0>(tmp[i]);
		}
		S[pos].clear();
		for (int i = 0; i < (int)tmp.size(); i++) S[pos].push_back(get<2>(tmp[i]));
		if (par != -1) S[pos].push_back(par);
		return make_pair(dp_tmp, str);
	}
	
	// Get DFS Order in Graph S
	void DFSOrder(int pos, int par) {
		tmp_DFSord.push_back(pos);
		for (int to : S[pos]) {
			if (to == par) continue;
			DFSOrder(to, pos);
		}
	}
	vector<int> GetDFSOrder(int pos, int par) {
		tmp_DFSord.clear();
		DFSOrder(pos, par);
		return tmp_DFSord;
	}
	
	// Get BFS order in Graph S
	void GetBFSOrder(int gr, int stt) {
		queue<int> Q; Q.push(stt); dist[stt] = 0;
		int ordcnt = 0;
		while(!Q.empty()) {
			int pos = Q.front(); Q.pop();
			Group[pos] = gr;
			GroupID[pos] = ordcnt; ordcnt += 1;
			for (int to : S[pos]) {
				if (dist[to] != -1) continue;
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
	
};


void Init(int n, vector<int> u, vector<int> v) {
	AllInit();
	if (Scenario == 0) Initialize();
	Scenario += 1;
	
	// Step #1. Copy (N, U, V)
	N = n;
	for (int i = 0; i < N - 1; i++) U[i] = u[i];
	for (int i = 0; i < N - 1; i++) V[i] = v[i];
	for (int i = 0; i < N; i++) G[i].clear();
	for (int i = 0; i < N - 1; i++) {
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	
	// Step #2. Get Diameter [Part 1]
	for (int i = 0; i < N; i++) dist[i] = -1;
	MakeDist2(N, 0);
	pair<int, int> e1 = make_pair(-1, -1);
	for (int i = 0; i < N; i++) e1 = max(e1, make_pair(dist[i], i));
	for (int i = 0; i < N; i++) dia1[i] = dist[i];
	
	// Step #3. Get Diameter [Part 2]
	for (int i = 0; i < N; i++) dist[i] = -1;
	MakeDist2(N, e1.second);
	pair<int, int> e2 = make_pair(-1, -1);
	for (int i = 0; i < N; i++) e2 = max(e2, make_pair(dist[i], i));
	for (int i = 0; i < N; i++) dia2[i] = dist[i];
	
	// Step #4. Get Root
	int MainRoot = 0, maxscore = 1000000;
	for (int i = 0; i < N; i++) {
		if (G[i].size() <= 2 && maxscore > max(dia1[i], dia2[i])) {
			maxscore = max(dia1[i], dia2[i]);
			MainRoot = i;
		}
	}
	
	// Step #5. Division of Tree [Part 1]
	for (int i = 0; i < N; i++) dp[i] = 0;
	for (int i = 0; i < N; i++) dist[i] = -1;
	for (int i = 0; i < N; i++) Group[i] = -1;
	for (int i = 0; i < N; i++) GroupID[i] = -1;
	dfs_Division(MainRoot);
	Root.push_back(MainRoot);
	
	// Step #6. Get "Root of Group"
	MakeDist2(N, MainRoot);
	vector<pair<int, int>> Root_tmp;
	for (int i : Root) Root_tmp.push_back(make_pair(dist[i], i));
	sort(Root_tmp.begin(), Root_tmp.end());
	Root.clear();
	for (int i = 0; i < (int)Root_tmp.size(); i++) Root.push_back(Root_tmp[i].second);
	
	// Step #7. Add Vertices to 13
	NumVertices = N;
	for (int i = 0; i < (int)Root.size(); i++) {
		int root = Root[i];
		for (int nex : S[root]) {
			int cx = nex, pa = root;
			while (true) {
				bool flag = false;
				for (int to : S[cx]) {
					if (pa == to) continue;
					pa = cx; cx = to; flag = true; break;
				}
				if (flag == false) break;
			}
			int cur = cx;
			for (int j = 0; j < 6 - dp[nex]; j++) {
				S[cur].push_back(NumVertices);
				S[NumVertices].push_back(cur);
				cur = NumVertices;
				NumVertices += 1;
			}
		}
		while (S[root].size() < 2) {
			int cur = root;
			for (int j = 0; j < 6; j++) {
				S[cur].push_back(NumVertices);
				S[NumVertices].push_back(cur);
				cur = NumVertices;
				NumVertices += 1;
			}
		}
	}
	
	// Step #8. Add Vertices to 14
	for (int i = 0; i < (int)Root.size(); i++) {
		string str = dfs_GetString(Root[i], -1).second;
		int LeftID = -1, RightID = -1;
		for (int j = 0; j < 11; j++) {
			if (str.substr(1, 10) == TreeList6[j]) LeftID = j;
			if (str.substr(13, 10) == TreeList6[j]) RightID = j;
		}
		if (LeftID < RightID) {
			swap(LeftID, RightID);
			swap(S[Root[i]][0], S[Root[i]][1]);
		}
		vector<int> Dord = GetDFSOrder(S[Root[i]][0], Root[i]);
		if (LeftID == 0) { S[Dord[3]].push_back(NumVertices); S[NumVertices].push_back(Dord[3]); NumVertices += 1; }
		if (LeftID == 1) { S[Dord[3]].push_back(NumVertices); S[NumVertices].push_back(Dord[3]); NumVertices += 1; }
		if (LeftID == 2) { S[Dord[2]].push_back(NumVertices); S[NumVertices].push_back(Dord[2]); NumVertices += 1; }
		if (LeftID == 3) { S[Dord[3]].push_back(NumVertices); S[NumVertices].push_back(Dord[3]); NumVertices += 1; }
		if (LeftID == 4) { S[Dord[4]].push_back(NumVertices); S[NumVertices].push_back(Dord[4]); NumVertices += 1; }
		if (LeftID == 5) { S[Dord[5]].push_back(NumVertices); S[NumVertices].push_back(Dord[5]); NumVertices += 1; }
		if (LeftID == 6) { S[Dord[2]].push_back(NumVertices); S[NumVertices].push_back(Dord[2]); NumVertices += 1; }
		if (LeftID == 7) { S[Dord[1]].push_back(NumVertices); S[NumVertices].push_back(Dord[1]); NumVertices += 1; }
		if (LeftID == 8) { S[Dord[0]].push_back(NumVertices); S[NumVertices].push_back(Dord[0]); NumVertices += 1; }
		if (LeftID == 9) { S[Dord[2]].push_back(NumVertices); S[NumVertices].push_back(Dord[2]); NumVertices += 1; }
		if (LeftID ==10) { S[Dord[3]].push_back(NumVertices); S[NumVertices].push_back(Dord[3]); NumVertices += 1; }
	}
	
	// Step #9. Division of Tree [Part 3]
	for (int i = 0; i < NumVertices; i++) dist[i] = -1;
	for (int i = 0; i < (int)Root.size(); i++) {
		string str = dfs_GetString(Root[i], -1).second;
		GroupTree[i] = Map[str];
		GetBFSOrder(i, Root[i]);
	}
	
	// Step #10. Set Value
	for (int i = 0; i < N; i++) {
		SetID(i, Group[i] * 14 + GroupID[i]);
	}
}

string SendA(string S) {
	// Step #1. Get (GroupX, GroupY)
	int Rank = StringToNumber(S, 20);
	int GroupX = -1, GroupY = -1, Rankcnt = 0;
	for (int i = 0; i < 1430; i++) {
		for (int j = i; j < 1430; j++) {
			if (Rankcnt == Rank) { GroupX = i; GroupY = j; }
			Rankcnt += 1;
		}
	}
	
	// Step #2. Send Tree
	if (GroupX == GroupY) {
		return NumberToString(GroupTree[GroupX], 20);
	}
	
	// Step #3. Send when "GroupX != GroupY"
	if (GroupX != GroupY) {
		MakeDist2(N, Root[GroupY]);
		int dst_path = 1000000, dst_id = -1;
		for (int i = 0; i < N; i++) {
			if (Group[i] != GroupX || dst_path <= dist[i]) continue;
			dst_path = dist[i];
			dst_id = GroupID[i];
		}
		int Ret = 0;
		if (dst_path < 5020) {
			int TreeNumX = GroupTree[GroupX];
			int TreeNumY = GroupTree[GroupY];
			Ret += TreeID2[TreeNumX][dst_id];
			Ret += TreeID1[TreeNumY] * 290;
			Ret += dst_path * 290 * 21;
		}
		else {
			int TreeNumX = GroupTree[GroupX];
			int TreeNumY = GroupTree[GroupY];
			Ret = 5020 * 290 * 21;
			Ret += TreeID1[TreeNumX];
			Ret += TreeID1[TreeNumY] * 21;
			Ret += (dst_path - 5020) * 21 * 21;
		}
		
		// Return
		for (int i = 1; i < 30; i++) {
			if (Ret >= (1 << i)) Ret -= (1 << i);
			else return NumberToString(Ret, i);
		}
	}
}
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	
	// Variables
	const int LIMIT1 = 7;
	const int LIMIT2 = 13;
	int Scenario = 0;
	int N;
	int X, GroupX, NumX;
	int Y, GroupY, NumY;
	
	// Tree Division & Distance
	int ord[20029], dp[20029]; string dp2[20029];
	int dist[20029];
	vector<int> G[20029];
	
	// List of Tree
	map<string, int> Map;
	string Tree[400]; int Treecnt = 0;
	vector<int> Treeord[400];
	vector<int> Treeds1[400]; int TreeID1[400];
	vector<int> Treeds2[400][15]; int TreeID2[400][15];
	vector<vector<int>> TreeList1, TreeList2;
	
	// List of Small Trees
	vector<string> TreeList7 = {
		"000011100111", // [0]
		"000011011011", // [1]
		"000001101111", // [2]
		"000110110011", // [3]
		"000011011101"  // [4]
	};
	vector<string> TreeList6 = {
		"0001100111",  // Group 0
		"0001011011",  // Group 1
		"0000111011",  // Group 1
		"0000011111",  // Group 2
		"0000101111",  // Group 2
		"0001101101",  // Group 3
		"0010110011",  // Group 3
		"0001110011",  // Group 3
		"0000110111",  // Group 4
		"0000111101",  // Group 4
		"0001011101"   // Group 4
	};
	
	void AllInit() {
		for (int i = 0; i < 20029; i++) {
			ord[i] = 0; dist[i] = 0;
			G[i].clear();
		}
	}
	
	void MakeGraph(int Vertices, string ss) {
		for (int i = 0; i < Vertices; i++) G[i].clear();
		int num = 1; stack<int> S; S.push(0);
		for (int i = 0; i < (int)ss.size(); i++) {
			if (ss[i] == '0') {
				G[S.top()].push_back(num);
				G[num].push_back(S.top());
				S.push(num); num += 1;
			}
			if (ss[i] == '1') S.pop();
		}
	}
	
	void Get_DP(int pos, int par) {
		dp[pos] = 1;
		dp2[pos] = "";
		for (int to : G[pos]) {
			if (to == par) continue;
			Get_DP(to, pos);
			dp2[pos] += ("0" + dp2[to] + "1");
			dp[pos] += dp[to];
		}
	}
	
	void MakeDist1(int Vertices, int stt) {
		for (int i = 0; i < Vertices; i++) dist[i] = -1;
		queue<int> Q; Q.push(stt); dist[stt] = 0;
		int ordcnt = 0;
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			ord[pos] = ordcnt; ordcnt += 1;
			for (int to : G[pos]) {
				if (dist[to] != -1) continue;
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
	
	void MakeDist2(int Vertices, int stt) {
		for (int i = 0; i < Vertices; i++) dist[i] = -1;
		queue<int> Q; Q.push(stt); dist[stt] = 0;
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			for (int to : G[pos]) {
				if (dist[to] != -1) continue;
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
	
	void ListUpTree() {
		int Level[11] = {0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
		for (int i = 0; i < 11; i++) {
			for (int j = Level[i]; j < 5; j++) {
				string ss = "";
				ss += "0"; ss += TreeList7[j]; ss += "1";
				ss += "0"; ss += TreeList6[i]; ss += "1";
				
				// EndPoint
				vector<bool> EndPoint(14, false);
				if (j == 1) { EndPoint[3] = true; }
				if (j == 2) { EndPoint[4] = true; }
				if (j == 3) { EndPoint[2] = true; }
				if (j == 4) { EndPoint[1] = true; EndPoint[3] = true; }
				
				// Make Graph
				MakeGraph(14, ss);
				Map[ss] = Treecnt;
				Tree[Treecnt] = ss;
				
				// Get Distance
				MakeDist1(14, 0);
				Treeds1[Treecnt] = vector<int>(14, 0);
				for (int i = 0; i < 14; i++) Treeds1[Treecnt][ord[i]] = dist[i];
				for (int i = 0; i < 14; i++) {
					if (G[i].size() == 3 && EndPoint[i] == false) {
						Treeds2[Treecnt][ord[i]] = vector<int>(14, -1);
					}
					else {
						MakeDist2(14, i);
						Treeds2[Treecnt][ord[i]] = vector<int>(14, 0);
						for (int j = 0; j < 14; j++) Treeds2[Treecnt][ord[i]][ord[j]] = dist[j];
					}
				}
				
				// Record Tree (ord, Treecnt++)
				Treeord[Treecnt] = vector<int>(14, 0);
				for (int i = 0; i < 14; i++) Treeord[Treecnt][i] = ord[i];
				Treecnt += 1;
			}
		}
	}
	
	void Initialize() {
		for (int i = 0; i < 400; i++) {
			TreeID1[i] = -1;
			for (int j = 0; j < 15; j++) TreeID2[i][j] = -1;
		}
		ListUpTree();
		for (int i = 0; i < Treecnt; i++) {
			int Verts = Tree[i].size() / 2 + 1;
			TreeList1.push_back(Treeds1[i]);
			for (int j = 0; j < Verts; j++) {
				if (Treeds2[i][j][0] != -1) TreeList2.push_back(Treeds2[i][j]);
			}
		}
		sort(TreeList1.begin(), TreeList1.end()); TreeList1.erase(unique(TreeList1.begin(), TreeList1.end()), TreeList1.end());
		sort(TreeList2.begin(), TreeList2.end()); TreeList2.erase(unique(TreeList2.begin(), TreeList2.end()), TreeList2.end());
		for (int i = 0; i < Treecnt; i++) {
			int Verts = Tree[i].size() / 2 + 1;
			TreeID1[i] = lower_bound(TreeList1.begin(), TreeList1.end(), Treeds1[i]) - TreeList1.begin();
			for (int j = 0; j < Verts; j++) {
				if (Treeds2[i][j][0] == -1) TreeID2[i][j] = -1;
				else TreeID2[i][j] = lower_bound(TreeList2.begin(), TreeList2.end(), Treeds2[i][j]) - TreeList2.begin();
			}
		}
		//cout << Treecnt << " " << TreeList1.size() << " " << TreeList2.size() << endl;
	}
	
	// Number -> String
	string NumberToString(long long val, int LEN) {
		string str = "";
		for (int i = 0; i < LEN; i++) {
			if ((val & (1LL << i)) == 0) str += "0";
			if ((val & (1LL << i)) != 0) str += "1";
		}
		return str;
	}
	
	// String -> Number
	int StringToNumber(string str, int LEN) {
		long long val = 0;
		for (int i = 0; i < LEN; i++) {
			if (str[i] == '1') val += (1LL << i);
		}
		return val;
	}
	
};

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

int Answer(string T) {
	// Step #1. When GroupX == GroupY
	if (GroupX == GroupY) {
		int idx = StringToNumber(T, 20);
		int Verts = Tree[idx].size() / 2 + 1;
		int RepX = -1, RepY = -1;
		for (int i = 0; i < Verts; i++) {
			if (Treeord[idx][i] == NumX) RepX = i;
			if (Treeord[idx][i] == NumY) RepY = i;
		}
		MakeGraph(Verts, Tree[idx]);
		MakeDist2(Verts, RepX);
		return dist[RepY];
	}
	
	// If the group is not same
	if (GroupX != GroupY) {
		int Recieve = StringToNumber(T, (int)T.size());
		for (int i = 1; i < (int)T.size(); i++) Recieve += (1 << i);
		
		if (Recieve >= 5020 * 290 * 21) {
			Recieve -= 5020 * 290 * 21;
			int id_X = Recieve % 21;
			int id_Y = (Recieve / 21) % 21;
			int d3 = (Recieve / (21 * 21)) + 5020;
			int d1 = 0, d2 = 0;
			for (int i = 0; i < Treecnt; i++) {
				if (TreeID1[i] == id_Y) d1 = Treeds1[i][NumY];
				if (TreeID1[i] == id_X) d2 = Treeds1[i][NumX];
			}
			return d1 + d2 + d3;
		}
		else {
			int id_X = Recieve % 290;
			int id_Y = (Recieve / 290) % 21;
			int d3 = (Recieve / (290 * 21));
			int d1 = 0, d2 = 0;
			for (int i = 0; i < Treecnt; i++) {
				if (TreeID1[i] == id_Y) d1 = Treeds1[i][NumY];
				int Verts = Tree[i].size() / 2 + 1;
				for (int j = 0; j < Verts; j++) {
					if (TreeID2[i][j] == id_X) d2 = Treeds2[i][j][NumX];
				}
			}
			return d1 + d2 + d3;
		}
	}
}

Compilation message

Ali.cpp: In function 'std::string SendA(std::string)':
Ali.cpp:450:1: warning: control reaches end of non-void function [-Wreturn-type]
  450 | }
      | ^
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:269:1: warning: control reaches end of non-void function [-Wreturn-type]
  269 | }
      | ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4496 KB Output is correct
2 Correct 6 ms 4496 KB Output is correct
3 Correct 7 ms 4496 KB Output is correct
4 Correct 5 ms 4496 KB Output is correct
5 Correct 7 ms 4496 KB Output is correct
6 Correct 19 ms 5616 KB Output is correct
7 Correct 19 ms 5544 KB Output is correct
8 Correct 24 ms 5476 KB Output is correct
9 Correct 19 ms 5604 KB Output is correct
10 Correct 18 ms 5880 KB Output is correct
11 Correct 19 ms 5480 KB Output is correct
12 Correct 15 ms 5356 KB Output is correct
13 Correct 16 ms 5376 KB Output is correct
14 Correct 19 ms 5712 KB Output is correct
15 Correct 23 ms 6020 KB Output is correct
16 Correct 17 ms 5416 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4500 KB Output is correct
2 Correct 153 ms 6148 KB Output is correct
3 Correct 129 ms 4692 KB Output is correct
4 Correct 688 ms 5608 KB Output is correct
5 Correct 692 ms 5696 KB Output is correct
6 Correct 763 ms 5660 KB Output is correct
7 Correct 732 ms 6136 KB Output is correct
8 Correct 743 ms 5716 KB Output is correct
9 Correct 712 ms 5960 KB Output is correct
10 Correct 719 ms 6344 KB Output is correct
11 Correct 661 ms 5676 KB Output is correct
12 Correct 163 ms 5512 KB Output is correct
13 Correct 439 ms 5848 KB Output is correct
14 Correct 479 ms 5860 KB Output is correct
15 Correct 111 ms 4524 KB Output is correct
16 Correct 661 ms 6132 KB Output is correct
17 Correct 679 ms 6124 KB Output is correct
18 Correct 655 ms 5936 KB Output is correct
19 Correct 645 ms 6072 KB Output is correct
20 Correct 425 ms 5976 KB Output is correct
21 Correct 589 ms 6040 KB Output is correct
22 Correct 480 ms 5540 KB Output is correct
23 Correct 505 ms 5684 KB Output is correct
24 Correct 526 ms 5556 KB Output is correct
25 Correct 498 ms 5544 KB Output is correct
26 Correct 487 ms 5480 KB Output is correct
27 Correct 479 ms 5600 KB Output is correct
28 Correct 471 ms 5536 KB Output is correct
29 Correct 481 ms 5580 KB Output is correct
30 Correct 460 ms 5444 KB Output is correct
31 Correct 468 ms 5452 KB Output is correct
32 Correct 489 ms 5436 KB Output is correct
33 Correct 463 ms 5444 KB Output is correct
34 Correct 471 ms 5592 KB Output is correct
35 Correct 484 ms 5452 KB Output is correct
36 Correct 487 ms 5504 KB Output is correct
37 Correct 497 ms 5660 KB Output is correct
38 Correct 474 ms 5500 KB Output is correct
39 Correct 89 ms 5484 KB Output is correct
40 Correct 734 ms 6172 KB Output is correct