제출 #544501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544501		model_code	Flights (JOI22_flights)	C++17	59 / 100	622 ms	3884 KiB

Ali

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

namespace {
	
	const int LIMIT1 = 7;
	const int LIMIT2 = 13;
	const int BACKET = 4;
	
	// Memo
	int Cnt = 0, Rank;
	
	// Graph
	int MainRoot = -1;
	int N, U[10009], V[100009];
	int dist[10009];
	int Par[10009];
	vector<int> G[10009];
	
	// Group Division
	int groupcnt = 0;
	int group[10009];      // Group ID
	int groupnum[10009];   // Vertex ID in group
	int dp[10009];
	vector<int> S[10009];  // Connect or Cut
	vector<int> Gr[10009]; // Group Division
		
	void AllInit() {
		Cnt = 0; Rank = 0;
		groupcnt = 0; MainRoot = -1;
		for (int i = 0; i < 10009; i++) {
			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();
		}
	}
};

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];
		}
	}
}

void dfs2(int pos, int par) {
	group[pos] = groupcnt;
	groupnum[pos] = (int)Gr[groupcnt].size();
	Gr[groupcnt].push_back(pos);
	for (int to : S[pos]) {
		if (to == par) continue;
		dfs2(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 Init(int n, vector<int> u, vector<int> v) {
	AllInit();
	
	// 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; }
	}
	
	// Get Distance
	for (int i = 0; i < N; i++) dist[i] = -1;
	dfs3(MainRoot, 0);
	vector<pair<int, int>> DistSort;
	for (int i = 0; i < N; i++) DistSort.push_back(make_pair(dist[i], i));
	sort(DistSort.begin(), DistSort.end());
	
	// Group Division
	dfs1(MainRoot, -1);
	for (int i = 0; i < N; i++) group[i] = -1;
	for (int i = 0; i < N; i++) {
		int idx = DistSort[i].second;
		if (group[idx] != -1) continue;
		dfs2(idx, -1);
		groupcnt += 1;
	}
	
	// Set ID
	for (int i = 0; i < groupcnt; i++) {
		for (int j = 0; j < (int)Gr[i].size(); j++) {
			SetID(Gr[i][j], LIMIT2 * i + j);
		}
	}
}

string SendA(string S) {
	// Get Group Number
	int GX = 0, GY = 0;
	for (int i = 0; i < 20; i++) {
		if (S[i] == '1') Rank += (1 << i);
	}
	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) {
		string str = "";
		for (int i = 0; i < N - 1; i++) {
			if (group[U[i]] != GX || group[V[i]] != GY) continue;
			for (int j = 0; j < BACKET; j++) {
				if ((groupnum[U[i]] & (1 << j)) == 0) str += "0";
				if ((groupnum[U[i]] & (1 << j)) != 0) str += "1";
			}
			for (int j = 0; j < BACKET; j++) {
				if ((groupnum[V[i]] & (1 << j)) == 0) str += "0";
				if ((groupnum[V[i]] & (1 << j)) != 0) str += "1";
			}
		}
		return str;
	}
	
	// Get String When GX != GY
	if (GX != GY) {
		string str = "";
		
		// Get GX-GY Path
		bool IsSwap = false;
		if (dist[Gr[GX][0]] > dist[Gr[GY][0]]) { swap(GX, GY); IsSwap = true; }
		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];
		if (IsSwap == true) { swap(u1, u2); swap(GX, GY); }
		
		// Get Distance from [Rep. of GX]
		for (int i = 0; i < N; i++) dist[i] = -1;
		dfs3(u1, 0);
		for (int i = 0; i < (int)Gr[GX].size(); i++) {
			for (int j = 0; j < BACKET; j++) {
				if ((dist[Gr[GX][i]] & (1 << j)) == 0) str += "0";
				if ((dist[Gr[GX][i]] & (1 << j)) != 0) str += "1";
			}
		}
		while (str.size() < LIMIT2 * BACKET) str += "0";
		
		// Get Distance from [Rep. of GY]
		for (int i = 0; i < N; i++) dist[i] = -1;
		dfs3(u2, 0);
		for (int i = 0; i < (int)Gr[GY].size(); i++) {
			for (int j = 0; j < BACKET; j++) {
				if ((dist[Gr[GY][i]] & (1 << j)) == 0) str += "0";
				if ((dist[Gr[GY][i]] & (1 << j)) != 0) str += "1";
			}
		}
		while (str.size() < LIMIT2 * BACKET * 2) str += "0";
		
		// Get Distance between u1 and u2
		for (int i = 0; i < N; i++) dist[i] = -1;
		dfs3(u1, 0);
		for (int j = 0; j < 14; j++) {
			if ((dist[u2] & (1 << j)) == 0) str += "0";
			if ((dist[u2] & (1 << j)) != 0) str += "1";
		}
		return str;
	}
}

Benjamin

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

namespace {
	
	const int LIMIT2 = 13;
	const int BACKET = 4;
	
	// Group
	int N, X, Y;
	int Cnt = 0, Rank;
	int GroupX, NumX;
	int GroupY, NumY;
	
	// Graph
	vector<int> G[10009];
	int dist[10009];
	
	void AllInit() {
		Cnt = 0; Rank = 0;
		for (int i = 0; i < 10009; i++) {
			G[i].clear(); dist[i] = 0;
		}
	}
};

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

string SendB(int n, int x, int y) {
	AllInit();
	
	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
	string str = "";
	for (int i = 0; i < 20; i++) {
		if ((Rank & (1 << i)) == 0) str += "0";
		if ((Rank & (1 << i)) != 0) str += "1";
	}
	return str;
}

int Answer(string T) {
	// If the group is same
	if (GroupX == GroupY) {
		for (int i = 0; i < (int)T.size() / (BACKET * 2); i++) {
			int u1 = 0, u2 = 0;
			for (int j = 0; j < BACKET; j++) {
				if (T[i * BACKET * 2 + j] == '1') u1 += (1 << j);
				if (T[i * BACKET * 2 + BACKET + j] == '1') u2 += (1 << j);
			}
			G[u1].push_back(u2);
			G[u2].push_back(u1);
		}
		for (int i = 0; i < N; i++) dist[i] = -1;
		dfs4(NumX, 0);
		return dist[NumY];
	}
	
	// If the group is not same
	if (GroupX != GroupY) {
		int d1 = 0, d2 = 0, d3 = 0;
		for (int i = 0; i < BACKET; i++) {
			if (T[NumX * BACKET + i] == '1') d1 += (1 << i);
			if (T[(LIMIT2 + NumY) * BACKET + i] == '1') d2 += (1 << i);
		}
		for (int i = 0; i < 14; i++) {
			if (T[LIMIT2 * BACKET * 2 + i] == '1') d3 += (1 << i);
		}
		return d1 + d2 + d3;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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