Submission #927072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927072	2024-02-14T08:30:45 Z	socpite	한자 끝말잇기 (JOI14_kanji)	C++14	91 / 100	135 ms	18828 KB

Anna

#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;

const long long INF = LLONG_MAX/2;
const int maxn = 305;

namespace anna{
  	vector<pair<int, int>> g[maxn];

	vector<long long> shortest_path(int N, int s, long long C[]){
		vector<long long> d(N, INF);
		vector<int> vis(N, 0);
		d[s] = 0;
		for(int i = 1; i <= N; i++){
			long long best = INF;
			int x = -1;
			for(int j = 0; j < N; j++){
				if(vis[j])continue;
				if(d[j] < best){
					best = d[j];
					x = j;
				}
			}
			if(x == -1)break;
			vis[x] = 1;
			for(auto v: g[x]) if(d[v.first] > C[v.second] + best)d[v.first] = C[v.second] + best;
		}
		return d;
	}

	

	void solve(int K, int Q, vector<long long>& forgor_C, vector<vector<long long>>& cost_to_T){
		// eval(i, x) = forgor(x) + cost_to_T
		vector<vector<int>> queries(K+1);
		for(int i = 0; i < Q; i++)queries[0].push_back(i);
		for(int b = 1; b <= K; b++){
			for(int a = 0; a < b; a++){
				vector<int> a_wins;
				for(auto v: queries[a]){
					if(forgor_C[a] + cost_to_T[a][v] < forgor_C[b] + cost_to_T[b][v])a_wins.push_back(v);
					else queries[b].push_back(v);
				}
				int cases = queries[a].size() + 1, num = a_wins.size();
				for(int i = 0; cases > 1; i++){
					Tap(num&1);
					num>>=1;
					cases = (cases+1)>>1;
				}
				queries[a] = a_wins;
			}
		}
	}
}


void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
	vector<long long> forgor_C(K+1, 0);
	vector<vector<long long>> cost_to_T(K+1, vector<long long>(Q));
	for(int i = 0; i < K; i++){
		forgor_C[i] = C[U[i]];
	}	
	for(int i = 0; i < K; i++)C[U[i]] = INF;
	for(int i = 0; i < M; i++){
		anna::g[A[i]].push_back({B[i], i});
	}
	for(int i = 0; i < K; i++){
		auto d = anna::shortest_path(N, B[U[i]], C);
		for(int j = 0; j < Q; j++)cost_to_T[i][j] = d[T[j]];
	}
	for(int i = 0; i < Q; i++){
		auto d = anna::shortest_path(N, S[i], C);
		for(int j = 0; j < K; j++)cost_to_T[j][i] += d[A[U[j]]];
		cost_to_T[K][i] = d[T[i]];
	}
	anna::solve(K, Q, forgor_C, cost_to_T);
	// eval(i, x) = forgor(x) + cost_to_A + cost_to_T



}

Bruno

#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;


const int maxn = 305;
const long long INF = 1e16*maxn;

namespace bruno {
  	vector<pair<int, int>> g[maxn];

	vector<long long> shortest_path(int N, int s, long long C[]){
		vector<long long> d(N, INF);
		vector<int> vis(N, 0);
		d[s] = 0;
		for(int i = 1; i <= N; i++){
			long long best = INF;
			int x = -1;
			for(int j = 0; j < N; j++){
				if(vis[j])continue;
				if(d[j] < best){
					best = d[j];
					x = j;
				}
			}
			if(x == -1)break;
			vis[x] = 1;
			for(auto v: g[x]) if(d[v.first] > C[v.second] + best)d[v.first] = C[v.second] + best;
		}
		return d;
	}

	vector<int> path[60];

	vector<int> solve_query(int N, int s, int t, long long C[]){
		vector<long long> d(N, INF);
		vector<int> vis(N, 0);
		vector<pair<int, int>> trace(N);
		d[s] = 0;
		for(int i = 1; i <= N; i++){
			long long best = INF;
			int x = -1;
			for(int j = 0; j < N; j++){
				if(vis[j])continue;
				if(d[j] < best){
					best = d[j];
					x = j;
				}
			}
			if(x == -1)break;
			vis[x] = 1;
			for(auto v: g[x]) if(d[v.first] > C[v.second] + best){
				d[v.first] = C[v.second] + best;
				trace[v.first] = {x, v.second};
			}
		}
		vector<int> ans;
		while(t != s){
			ans.push_back(trace[t].second);
			t = trace[t].first;
		}
		reverse(ans.begin(), ans.end());
		return ans;
	}

	vector<vector<int>> solve(int K, int Q, vector<vector<long long>>& cost_to_T, int &ptr, int X[]){
		vector<vector<int>> queries(K+1);
		for(int i = 0; i < Q; i++)queries[0].push_back(i);
		for(int b = 1; b <= K; b++){
			for(int a = 0; a < b; a++){

				auto cmp = [&a, &b, &cost_to_T](int lhs, int rhs){
					return cost_to_T[a][lhs] - cost_to_T[b][lhs] < cost_to_T[a][rhs] - cost_to_T[b][rhs];  
				};

				int cases = queries[a].size() + 1, num = 0;
				for(int i = 0; cases > 1; i++){
					num ^= X[ptr++]<<i;
					cases = (cases+1)>>1;
				}
				
				sort(queries[a].begin(), queries[a].end(), cmp);
				while(queries[a].size() > num){
					queries[b].push_back(queries[a].back());
					queries[a].pop_back();
				}
			}
		}
		return queries;
	}
}

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
	vector<vector<long long>> cost_to_T(K+1, vector<long long>(Q));
	for(int i = 0; i < K; i++)C[U[i]] = INF;
	for(int i = 0; i < M; i++){
		bruno::g[A[i]].push_back({B[i], i});
	}
	for(int i = 0; i < K; i++){
		auto d = bruno::shortest_path(N, B[U[i]], C);
		for(int j = 0; j < Q; j++)cost_to_T[i][j] = d[T[j]];
	}
	for(int i = 0; i < Q; i++){
		auto d = bruno::shortest_path(N, S[i], C);
		for(int j = 0; j < K; j++)cost_to_T[j][i] += d[A[U[j]]];
		cost_to_T[K][i] = d[T[i]];
	};
	int ptr = 0;
	auto qtypes = bruno::solve(K, Q, cost_to_T, ptr, X);
	for(int i = 0; i <= K; i++){
		if(i < K)C[U[i]] = 0;
		for(auto v: qtypes[i]){
			bruno::path[v] = bruno::solve_query(N, S[v], T[v], C);
			if(i == K)for(auto ele: bruno::path[v]){
				for(int j = 0; j < K; j++)assert(ele != U[j]);
			}
		}
		if(i < K)C[U[i]] = INF;
	}
	for(int i = 0; i < Q; i++){
		for(auto v: bruno::path[i])Answer(v);
		Answer(-1);
	}
}

Compilation message

Bruno.cpp: In function 'std::vector<std::vector<int> > bruno::solve(int, int, std::vector<std::vector<long long int> >&, int&, int*)':
Bruno.cpp:83:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     while(queries[a].size() > num){
      |           ~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	4396 KB	Output is correct - L = 31
2	Correct	9 ms	4396 KB	Output is correct - L = 25
3	Correct	8 ms	4400 KB	Output is correct - L = 27
4	Correct	7 ms	4384 KB	Output is correct - L = 29
5	Correct	7 ms	4392 KB	Output is correct - L = 27
6	Correct	7 ms	4392 KB	Output is correct - L = 27
7	Correct	8 ms	4380 KB	Output is correct - L = 32
8	Correct	9 ms	4400 KB	Output is correct - L = 20
9	Correct	11 ms	4416 KB	Output is correct - L = 20
10	Correct	13 ms	4724 KB	Output is correct - L = 20
11	Correct	4 ms	4388 KB	Output is correct - L = 5
12	Correct	77 ms	14248 KB	Output is correct - L = 20
13	Correct	5 ms	4388 KB	Output is correct - L = 31
14	Correct	4 ms	4388 KB	Output is correct - L = 1

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4896 KB	Output is correct - L = 67
2	Correct	30 ms	4828 KB	Output is correct - L = 68
3	Correct	25 ms	4908 KB	Output is correct - L = 57
4	Correct	27 ms	5160 KB	Output is correct - L = 61
5	Correct	23 ms	4384 KB	Output is correct - L = 70
6	Correct	28 ms	4904 KB	Output is correct - L = 65
7	Correct	25 ms	4960 KB	Output is correct - L = 46
8	Correct	30 ms	4916 KB	Output is correct - L = 66
9	Correct	10 ms	5172 KB	Output is correct - L = 68
10	Correct	10 ms	4916 KB	Output is correct - L = 69
11	Correct	10 ms	4912 KB	Output is correct - L = 68
12	Correct	32 ms	4968 KB	Output is correct - L = 66
13	Correct	124 ms	14372 KB	Output is correct - L = 33
14	Correct	28 ms	4928 KB	Output is correct - L = 66
15	Correct	27 ms	4944 KB	Output is correct - L = 56
16	Correct	38 ms	5008 KB	Output is correct - L = 35
17	Correct	34 ms	5064 KB	Output is correct - L = 42
18	Correct	37 ms	5488 KB	Output is correct - L = 50
19	Correct	13 ms	4652 KB	Output is correct - L = 44
20	Correct	30 ms	5908 KB	Output is correct - L = 62
21	Correct	41 ms	5896 KB	Output is correct - L = 30
22	Correct	12 ms	4908 KB	Output is correct - L = 69
23	Correct	10 ms	4920 KB	Output is correct - L = 67
24	Correct	10 ms	4912 KB	Output is correct - L = 69

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	4900 KB	Output is correct - L = 67
2	Correct	27 ms	4388 KB	Output is correct - L = 68
3	Correct	32 ms	4900 KB	Output is correct - L = 57
4	Correct	28 ms	4904 KB	Output is correct - L = 61
5	Correct	23 ms	4396 KB	Output is correct - L = 70
6	Correct	27 ms	4904 KB	Output is correct - L = 65
7	Correct	25 ms	4908 KB	Output is correct - L = 46
8	Correct	31 ms	4908 KB	Output is correct - L = 66
9	Correct	10 ms	4920 KB	Output is correct - L = 68
10	Correct	10 ms	4912 KB	Output is correct - L = 69
11	Correct	10 ms	4920 KB	Output is correct - L = 68
12	Correct	28 ms	4912 KB	Output is correct - L = 66
13	Correct	135 ms	14388 KB	Output is correct - L = 33
14	Correct	30 ms	5164 KB	Output is correct - L = 66
15	Correct	27 ms	4904 KB	Output is correct - L = 56
16	Correct	33 ms	4932 KB	Output is correct - L = 35
17	Correct	34 ms	4984 KB	Output is correct - L = 42
18	Correct	37 ms	5332 KB	Output is correct - L = 50
19	Correct	13 ms	4388 KB	Output is correct - L = 44
20	Correct	39 ms	5904 KB	Output is correct - L = 62
21	Correct	42 ms	6128 KB	Output is correct - L = 30
22	Correct	11 ms	4912 KB	Output is correct - L = 69
23	Correct	10 ms	4968 KB	Output is correct - L = 67
24	Correct	10 ms	5416 KB	Output is correct - L = 69

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4908 KB	Output is correct - L = 67
2	Correct	30 ms	4784 KB	Output is correct - L = 68
3	Correct	25 ms	4908 KB	Output is correct - L = 57
4	Correct	27 ms	4908 KB	Output is correct - L = 61
5	Correct	24 ms	4388 KB	Output is correct - L = 70
6	Correct	27 ms	4908 KB	Output is correct - L = 65
7	Correct	27 ms	4904 KB	Output is correct - L = 46
8	Correct	30 ms	4900 KB	Output is correct - L = 66
9	Correct	11 ms	4916 KB	Output is correct - L = 68
10	Correct	10 ms	4936 KB	Output is correct - L = 69
11	Correct	10 ms	4940 KB	Output is correct - L = 68
12	Correct	28 ms	4924 KB	Output is correct - L = 66
13	Correct	122 ms	18828 KB	Output is correct - L = 33
14	Correct	28 ms	4844 KB	Output is correct - L = 66
15	Correct	27 ms	4936 KB	Output is correct - L = 56
16	Correct	33 ms	4996 KB	Output is correct - L = 35
17	Correct	36 ms	5148 KB	Output is correct - L = 42
18	Correct	37 ms	5776 KB	Output is correct - L = 50
19	Correct	13 ms	4412 KB	Output is correct - L = 44
20	Correct	30 ms	6396 KB	Output is correct - L = 62
21	Correct	41 ms	6524 KB	Output is correct - L = 30
22	Correct	10 ms	4948 KB	Output is correct - L = 69
23	Correct	10 ms	4948 KB	Output is correct - L = 67
24	Correct	10 ms	4948 KB	Output is correct - L = 69

Subtask #5

11.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4908 KB	Output is partially correct - L = 67
2	Correct	27 ms	4392 KB	Output is partially correct - L = 68
3	Correct	25 ms	4896 KB	Output is correct - L = 57
4	Correct	27 ms	4908 KB	Output is correct - L = 61
5	Correct	24 ms	4404 KB	Output is partially correct - L = 70
6	Correct	27 ms	4912 KB	Output is partially correct - L = 65
7	Correct	25 ms	4912 KB	Output is correct - L = 46
8	Correct	27 ms	4952 KB	Output is partially correct - L = 66
9	Correct	10 ms	4920 KB	Output is partially correct - L = 68
10	Correct	10 ms	4988 KB	Output is partially correct - L = 69
11	Correct	10 ms	4912 KB	Output is partially correct - L = 68
12	Correct	30 ms	4964 KB	Output is partially correct - L = 66
13	Correct	123 ms	14624 KB	Output is correct - L = 33
14	Correct	27 ms	4932 KB	Output is partially correct - L = 66
15	Correct	27 ms	4904 KB	Output is correct - L = 56
16	Correct	35 ms	4972 KB	Output is correct - L = 35
17	Correct	34 ms	5156 KB	Output is correct - L = 42
18	Correct	43 ms	5296 KB	Output is correct - L = 50
19	Correct	13 ms	4400 KB	Output is correct - L = 44
20	Correct	30 ms	5988 KB	Output is correct - L = 62
21	Correct	41 ms	5900 KB	Output is correct - L = 30
22	Correct	10 ms	4920 KB	Output is partially correct - L = 69
23	Correct	10 ms	4916 KB	Output is partially correct - L = 67
24	Correct	11 ms	4920 KB	Output is partially correct - L = 69