oj.uz

답안 #544502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544502 2022-04-02T07:03:07 Z model_code Flights (JOI22_flights) C++17
95 / 100
 2083 ms 6944 KB 
#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);
		}
	}
}
#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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1090 ms 4136 KB Output is correct
2 Correct 1210 ms 4264 KB Output is correct
3 Correct 1244 ms 4148 KB Output is correct
4 Correct 1173 ms 4148 KB Output is correct
5 Correct 1185 ms 4164 KB Output is correct
6 Correct 1151 ms 5472 KB Output is correct
7 Correct 1193 ms 5568 KB Output is correct
8 Correct 1230 ms 5568 KB Output is correct
9 Correct 1178 ms 5548 KB Output is correct
10 Correct 1208 ms 5840 KB Output is correct
11 Correct 1130 ms 5420 KB Output is correct
12 Correct 1197 ms 5192 KB Output is correct
13 Correct 1191 ms 5188 KB Output is correct
14 Correct 1256 ms 5820 KB Output is correct
15 Correct 1144 ms 6612 KB Output is correct
16 Correct 1221 ms 5248 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1152 ms 4136 KB Output is correct
2 Partially correct 1283 ms 6840 KB Output is partially correct
3 Correct 1291 ms 4148 KB Output is correct
4 Correct 2029 ms 5704 KB Output is correct
5 Correct 2045 ms 5736 KB Output is correct
6 Correct 2050 ms 5876 KB Output is correct
7 Partially correct 2012 ms 6724 KB Output is partially correct
8 Correct 1878 ms 5776 KB Output is correct
9 Partially correct 1822 ms 6492 KB Output is partially correct
10 Partially correct 1948 ms 6868 KB Output is partially correct
11 Correct 2066 ms 5936 KB Output is correct
12 Correct 1472 ms 5632 KB Output is correct
13 Correct 1754 ms 6120 KB Output is correct
14 Correct 1725 ms 6072 KB Output is correct
15 Correct 1370 ms 4280 KB Output is correct
16 Partially correct 1794 ms 6944 KB Output is partially correct
17 Partially correct 1866 ms 6936 KB Output is partially correct
18 Partially correct 2083 ms 6552 KB Output is partially correct
19 Partially correct 1930 ms 6660 KB Output is partially correct
20 Partially correct 1712 ms 6516 KB Output is partially correct
21 Partially correct 1909 ms 6628 KB Output is partially correct
22 Correct 1814 ms 5436 KB Output is correct
23 Correct 1893 ms 5580 KB Output is correct
24 Correct 1819 ms 5360 KB Output is correct
25 Partially correct 1868 ms 5356 KB Output is partially correct
26 Correct 1777 ms 5400 KB Output is correct
27 Correct 1814 ms 5472 KB Output is correct
28 Correct 1765 ms 5372 KB Output is correct
29 Correct 1742 ms 5480 KB Output is correct
30 Correct 1861 ms 5260 KB Output is correct
31 Correct 1665 ms 5384 KB Output is correct
32 Correct 1863 ms 5360 KB Output is correct
33 Correct 1743 ms 5360 KB Output is correct
34 Correct 1701 ms 5336 KB Output is correct
35 Partially correct 1617 ms 5372 KB Output is partially correct
36 Correct 1658 ms 5372 KB Output is correct
37 Correct 1565 ms 5368 KB Output is correct
38 Correct 1555 ms 5344 KB Output is correct
39 Correct 1208 ms 5328 KB Output is correct
40 Partially correct 2055 ms 6748 KB Output is partially correct