oj.uz

Submission #544501

# Submission time Handle Problem Language Result Execution time Memory
544501 2022-04-02T07:03:05 Z model_code Flights (JOI22_flights) C++17
59 / 100
 622 ms 3884 KB 
#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;
	}
}
#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;
	}
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1680 KB Output is correct
2 Correct 4 ms 1680 KB Output is correct
3 Correct 4 ms 1680 KB Output is correct
4 Correct 4 ms 1756 KB Output is correct
5 Correct 4 ms 1680 KB Output is correct
6 Correct 15 ms 2784 KB Output is correct
7 Correct 17 ms 2776 KB Output is correct
8 Correct 16 ms 2800 KB Output is correct
9 Correct 26 ms 2700 KB Output is correct
10 Correct 18 ms 2996 KB Output is correct
11 Correct 13 ms 2572 KB Output is correct
12 Correct 19 ms 2744 KB Output is correct
13 Correct 16 ms 2756 KB Output is correct
14 Correct 12 ms 2816 KB Output is correct
15 Correct 18 ms 3636 KB Output is correct
16 Correct 13 ms 2904 KB Output is correct

Subtask #2
44.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 1792 KB Output is partially correct
2 Partially correct 158 ms 3640 KB Output is partially correct
3 Partially correct 130 ms 1840 KB Output is partially correct
4 Partially correct 575 ms 2964 KB Output is partially correct
5 Partially correct 550 ms 3048 KB Output is partially correct
6 Partially correct 622 ms 2944 KB Output is partially correct
7 Partially correct 537 ms 3884 KB Output is partially correct
8 Partially correct 617 ms 2968 KB Output is partially correct
9 Partially correct 443 ms 3368 KB Output is partially correct
10 Partially correct 412 ms 3708 KB Output is partially correct
11 Partially correct 517 ms 2892 KB Output is partially correct
12 Partially correct 168 ms 2588 KB Output is partially correct
13 Partially correct 322 ms 2880 KB Output is partially correct
14 Partially correct 356 ms 2896 KB Output is partially correct
15 Partially correct 175 ms 1724 KB Output is partially correct
16 Partially correct 504 ms 3692 KB Output is partially correct
17 Partially correct 398 ms 3612 KB Output is partially correct
18 Partially correct 455 ms 3524 KB Output is partially correct
19 Partially correct 422 ms 3460 KB Output is partially correct
20 Partially correct 386 ms 3288 KB Output is partially correct
21 Partially correct 463 ms 3492 KB Output is partially correct
22 Partially correct 460 ms 2868 KB Output is partially correct
23 Partially correct 515 ms 2920 KB Output is partially correct
24 Partially correct 430 ms 2936 KB Output is partially correct
25 Partially correct 466 ms 2844 KB Output is partially correct
26 Partially correct 447 ms 2860 KB Output is partially correct
27 Partially correct 466 ms 2940 KB Output is partially correct
28 Partially correct 481 ms 2872 KB Output is partially correct
29 Partially correct 467 ms 2864 KB Output is partially correct
30 Partially correct 494 ms 2956 KB Output is partially correct
31 Partially correct 439 ms 2928 KB Output is partially correct
32 Partially correct 462 ms 2856 KB Output is partially correct
33 Partially correct 472 ms 2936 KB Output is partially correct
34 Partially correct 416 ms 2920 KB Output is partially correct
35 Partially correct 460 ms 2952 KB Output is partially correct
36 Partially correct 420 ms 2904 KB Output is partially correct
37 Partially correct 421 ms 2956 KB Output is partially correct
38 Partially correct 496 ms 2864 KB Output is partially correct
39 Partially correct 74 ms 2848 KB Output is partially correct
40 Partially correct 584 ms 3500 KB Output is partially correct