oj.uz

Submission #927066

# Submission time Handle Problem Language Result Execution time Memory
927066 2024-02-14T08:16:02 Z socpite 한자 끝말잇기 (JOI14_kanji) C++14
40 / 100
 127 ms 18856 KB 
#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 a, int b, int K, vector<long long>& forgor_C, vector<vector<long long>>& cost_to_T, vector<int> queries){
		// eval(i, x) = forgor(x) + cost_to_T
		if(queries.empty())return;
		if(b == K+1){
			return;
		}
		vector<int> a_wins, b_wins;
		for(auto v: queries){
			if(forgor_C[a] + cost_to_T[a][v] < forgor_C[b] + cost_to_T[b][v]) a_wins.push_back(v);
			else b_wins.push_back(v);
		}
		int cases = queries.size() + 1, num = a_wins.size();
		for(int i = 0; cases > 1; i++){
			Tap(num&1);
			num>>=1;
			cases = (cases+1)>>1;
		}
		solve(a, b+1, K, forgor_C, cost_to_T, a_wins);
		solve(b, b+1, K, forgor_C, cost_to_T, b_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]];
	}
	vector<int> queries;
	for(int i = 0; i < Q; i++)queries.push_back(i);
	anna::solve(0, 1, K, forgor_C, cost_to_T, queries);
	// eval(i, x) = forgor(x) + cost_to_A + cost_to_T



}

#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> qtypes[6];
	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;
	}

	void solve(int a, int b, int K, vector<vector<long long>>& cost_to_T, vector<int> queries, int &ptr, int X[]){
		// eval(i, x) = forgor(x) + cost_to_T
		if(queries.empty())return;
		if(b == K+1){
			qtypes[a].insert(qtypes[a].end(), queries.begin(), queries.end());
			return;
		}
		vector<int> a_wins, b_wins;
		int cases = queries.size() + 1, num = 0;
		for(int i = 0; cases > 1; i++){
			num^=X[ptr++]<<i;
			cases = (cases+1)>>1;
		}
		assert(num < queries.size()+1);
		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];  
		};

		sort(queries.begin(), queries.end(), cmp);

		for(int i = 0; i < queries.size(); i++){
			if(i < num)a_wins.push_back(queries[i]);
			else b_wins.push_back(queries[i]);
		}

		solve(a, b+1, K, cost_to_T, a_wins, ptr, X);
		solve(b, b+1, K, cost_to_T, b_wins, ptr, X);

	}
}

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]];
	}
	vector<int> queries;
	for(int i = 0; i < Q; i++)queries.push_back(i);
	int ptr = 0;
	bruno::solve(0, 1, K, cost_to_T, queries, ptr, X);
	for(int i = 0; i <= K; i++){
		if(i < K)C[U[i]] = 0;
		for(auto v: bruno::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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Bruno.cpp:2:
Bruno.cpp: In function 'void bruno::solve(int, int, int, std::vector<std::vector<long long int> >&, std::vector<int>, int&, int*)':
Bruno.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   assert(num < queries.size()+1);
      |          ~~~~^~~~~~~~~~~~~~~~~~
Bruno.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i = 0; i < queries.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4416 KB Output is correct - L = 34
2 Correct 10 ms 4420 KB Output is correct - L = 26
3 Correct 7 ms 4420 KB Output is correct - L = 28
4 Correct 7 ms 4388 KB Output is correct - L = 29
5 Correct 8 ms 4908 KB Output is correct - L = 27
6 Correct 8 ms 4396 KB Output is correct - L = 27
7 Correct 8 ms 4392 KB Output is correct - L = 32
8 Correct 10 ms 4428 KB Output is correct - L = 20
9 Correct 11 ms 4728 KB Output is correct - L = 20
10 Correct 12 ms 4828 KB Output is correct - L = 20
11 Correct 4 ms 4412 KB Output is correct - L = 5
12 Correct 76 ms 18468 KB Output is correct - L = 20
13 Correct 6 ms 4420 KB Output is correct - L = 31
14 Correct 4 ms 4404 KB Output is correct - L = 1

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4932 KB Output is correct - L = 68
2 Correct 28 ms 4404 KB Output is correct - L = 69
3 Correct 26 ms 4920 KB Output is correct - L = 63
4 Correct 30 ms 4916 KB Output is correct - L = 64
5 Correct 25 ms 4416 KB Output is correct - L = 80
6 Correct 36 ms 4924 KB Output is correct - L = 75
7 Correct 26 ms 4932 KB Output is correct - L = 53
8 Correct 30 ms 4912 KB Output is correct - L = 74
9 Correct 11 ms 4940 KB Output is correct - L = 92
10 Correct 11 ms 4988 KB Output is correct - L = 93
11 Correct 12 ms 4948 KB Output is correct - L = 91
12 Correct 32 ms 4924 KB Output is correct - L = 79
13 Correct 119 ms 18556 KB Output is correct - L = 33
14 Correct 33 ms 4924 KB Output is correct - L = 73
15 Correct 28 ms 4932 KB Output is correct - L = 62
16 Correct 34 ms 4996 KB Output is correct - L = 50
17 Correct 36 ms 5340 KB Output is correct - L = 42
18 Correct 39 ms 5688 KB Output is correct - L = 50
19 Correct 13 ms 4408 KB Output is correct - L = 62
20 Correct 37 ms 6604 KB Output is correct - L = 66
21 Correct 43 ms 6372 KB Output is correct - L = 30
22 Correct 11 ms 4940 KB Output is correct - L = 91
23 Correct 11 ms 5284 KB Output is correct - L = 88
24 Correct 11 ms 4936 KB Output is correct - L = 90

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4924 KB Output is correct - L = 68
2 Correct 32 ms 4404 KB Output is correct - L = 69
3 Correct 28 ms 4928 KB Output is correct - L = 63
4 Correct 33 ms 4984 KB Output is correct - L = 64
5 Correct 24 ms 4412 KB Output is correct - L = 80
6 Correct 28 ms 4916 KB Output is correct - L = 75
7 Correct 26 ms 4936 KB Output is correct - L = 53
8 Correct 31 ms 4924 KB Output is correct - L = 74
9 Correct 14 ms 4960 KB Output is correct - L = 92
10 Correct 11 ms 4940 KB Output is correct - L = 93
11 Correct 11 ms 4804 KB Output is correct - L = 91
12 Correct 31 ms 4920 KB Output is correct - L = 79
13 Correct 127 ms 18592 KB Output is correct - L = 33
14 Correct 28 ms 4924 KB Output is correct - L = 73
15 Correct 28 ms 4948 KB Output is correct - L = 62
16 Correct 35 ms 4992 KB Output is correct - L = 50
17 Correct 38 ms 5372 KB Output is correct - L = 42
18 Correct 39 ms 5940 KB Output is correct - L = 50
19 Correct 13 ms 4560 KB Output is correct - L = 62
20 Correct 32 ms 6396 KB Output is correct - L = 66
21 Correct 44 ms 6552 KB Output is correct - L = 30
22 Correct 11 ms 4940 KB Output is correct - L = 91
23 Correct 11 ms 4936 KB Output is correct - L = 88
24 Correct 11 ms 4892 KB Output is correct - L = 90

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4920 KB Output is correct - L = 68
2 Correct 28 ms 4404 KB Output is correct - L = 69
3 Correct 26 ms 5164 KB Output is correct - L = 63
4 Correct 32 ms 4912 KB Output is correct - L = 64
5 Correct 28 ms 4412 KB Output is correct - L = 80
6 Correct 28 ms 5184 KB Output is correct - L = 75
7 Correct 26 ms 4776 KB Output is correct - L = 53
8 Correct 31 ms 4900 KB Output is correct - L = 74
9 Incorrect 11 ms 4948 KB Output isn't correct - L = 92
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5176 KB Output is partially correct - L = 68
2 Correct 30 ms 4812 KB Output is partially correct - L = 69
3 Correct 26 ms 4956 KB Output is correct - L = 63
4 Correct 28 ms 4924 KB Output is correct - L = 64
5 Correct 27 ms 4480 KB Output is partially correct - L = 80
6 Correct 28 ms 4916 KB Output is partially correct - L = 75
7 Correct 32 ms 5060 KB Output is correct - L = 53
8 Correct 32 ms 5060 KB Output is partially correct - L = 74
9 Correct 10 ms 4940 KB Output isn't correct - L = 92
10 Correct 11 ms 4940 KB Output isn't correct - L = 93
11 Correct 11 ms 4948 KB Output isn't correct - L = 91
12 Correct 31 ms 4932 KB Output is partially correct - L = 79
13 Correct 123 ms 18856 KB Output is correct - L = 33
14 Correct 30 ms 4920 KB Output is partially correct - L = 73
15 Correct 28 ms 4932 KB Output is correct - L = 62
16 Correct 34 ms 4980 KB Output is correct - L = 50
17 Correct 36 ms 5268 KB Output is correct - L = 42
18 Correct 39 ms 5764 KB Output is correct - L = 50
19 Correct 13 ms 4408 KB Output is correct - L = 62
20 Correct 30 ms 6412 KB Output is partially correct - L = 66
21 Correct 43 ms 6396 KB Output is correct - L = 30
22 Correct 11 ms 4944 KB Output isn't correct - L = 91
23 Correct 11 ms 4948 KB Output is partially correct - L = 88
24 Correct 11 ms 4940 KB Output isn't correct - L = 90