oj.uz

Submission #708221

# Submission time Handle Problem Language Result Execution time Memory
708221 2023-03-11T10:31:13 Z esomer Two Transportations (JOI19_transportations) C++17
100 / 100
 835 ms 48824 KB 
#include<bits/stdc++.h>
#include "Azer.h"
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

vector<int> dist;
set<pair<int, int>> s;
vector<vector<pair<int, int>>> adj;
int mn = 0, bit = 8, mine = 0, his = 0, bit2 = 10, nd = 0;
bool receiving = 0;

void Dijkstra(int nod){
	int n = (int)dist.size();
	priority_queue<pair<int, int>> q; q.push({-dist[nod], nod});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != nod) s.insert({dist[x], x});
		for(auto p : adj[x]){
			int node = p.first;
			if(dist[node] > dist[x] + p.second){
				s.erase({dist[node], node});
				dist[node] = dist[x] + p.second;
				q.push({-dist[node], node});
			}
		}
	}
}

void InitA(int n, int m, vector<int> U, vector<int> V, vector<int> C){
	dist.assign(n, 1e9); dist[0] = 0;
	adj.assign(n, {});
	for(int i = 0; i < m; i++){
		adj[U[i]].push_back({V[i], C[i]});
		adj[V[i]].push_back({U[i], C[i]});
	}
	Dijkstra(0);
	if(n == 1) return;
	for(int i = 1; i < n; i++){
		if(dist[i] == 1e9) s.insert({1e9, i});
	}
	int d = (*s.begin()).first;
	if(d > 500) d = 511;
	if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
	else SendA(0);
}

void start(){
	if((int)s.size() == 0) return;
	bit = 8; mine = 0; his = 0;
	int d = (*s.begin()).first; d -= mn;
	if(d > 500) d = 511;
	if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
	else SendA(0);
}

void ReceiveA(bool x){
	if(receiving){
		if(x) nd += (1 << bit2);
		bit2--;
		if(bit2 == -1){
			s.erase({dist[nd], nd});
			dist[nd] = mn;
			Dijkstra(nd);
			receiving = 0;
			nd = 0;
			bit2 = 10;
			start();
		}
		return;
	}
	if(x) his += (1 << bit);
	bit--;
	if(bit == -1){
		//Si él gana, simplemente receiving = 1, y return;
		//Si gano yo, le paso la info del nodo y luego hago start().
		mn += min(mine, his);
		if(mine <= his){//Para Baijan esto es < his.
			int node = (*s.begin()).second; s.erase(s.begin());
			for(int i = 10; i >= 0; i--){
				if((1 << i) & node) SendA(1);
				else SendA(0);
			}
			start();
		}else{
			receiving = 1;
		}
	}else{
		int d = (*s.begin()).first; d -= mn;
		if(d > 500) d = 511;
		if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
		else SendA(0);
	}
}

vector<int> Answer(){
	return dist;
}

#include<bits/stdc++.h>
#include "Baijan.h"
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

vector<int> distB;
set<pair<int, int>> sB;
vector<vector<pair<int, int>>> adjB;
int mnB = 0, bitB = 8, mineB = 0, hisB = 0, bit2B = 10, ndB = 0;
bool receivingB = 0;

void DijkstraB(int nod){
	int n = (int)distB.size();
	priority_queue<pair<int, int>> q; q.push({-distB[nod], nod});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != nod) sB.insert({distB[x], x});
		for(auto p : adjB[x]){
			int node = p.first;
			if(distB[node] > distB[x] + p.second){
				sB.erase({distB[node], node});
				distB[node] = distB[x] + p.second;
				q.push({-distB[node], node});
			}
		}
	}
}

void InitB(int n, int m, vector<int> U, vector<int> V, vector<int> C){
	distB.assign(n, 1e9); distB[0] = 0;
	adjB.assign(n, {});
	for(int i = 0; i < m; i++){
		adjB[U[i]].push_back({V[i], C[i]});
		adjB[V[i]].push_back({U[i], C[i]});
	}
	DijkstraB(0);
	if(n == 1) return;
	for(int i = 1; i < n; i++){
		if(distB[i] == 1e9) sB.insert({1e9, i});
	}
}

void ReceiveB(bool x){
	if(receivingB){
		if(x) ndB += (1 << bit2B);
		bit2B--;
		if(bit2B == -1){
			sB.erase({distB[ndB], ndB});
			distB[ndB] = mnB;
			DijkstraB(ndB);
			receivingB = 0;
			ndB = 0;
			bit2B = 10;
			bitB = 8; mineB = 0; hisB = 0;
		}
		return;
	}
	if(x) hisB += (1 << bitB);
	int d = (*sB.begin()).first; d -= mnB;
	if(d > 500) d = 511;
	if((1 << bitB) & d) {SendB(1); mineB += (1 << bitB);}
	else SendB(0);
	bitB--;
	if(bitB == -1){
		//Si él gana, simplemente receiving = 1, y return;
		//Si gano yo, le paso la info del nodo y luego hago start().
		//~ cout << "B mine " << mineB << " his " << hisB << endl;
		mnB += min(mineB, hisB);
		if(mineB < hisB){//Para Baijan esto es < his.
			int node = (*sB.begin()).second; sB.erase(sB.begin());
			for(int i = 10; i >= 0; i--){
				if((1 << i) & node) SendB(1);
				else SendB(0);
			}
			bitB = 8; mineB = 0; hisB = 0;
		}else{
			receivingB = 1;
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 988 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 468 ms 884 KB Output is correct
4 Correct 569 ms 10172 KB Output is correct
5 Correct 34 ms 656 KB Output is correct
6 Correct 494 ms 2340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 400 KB Output is correct
2 Correct 414 ms 976 KB Output is correct
3 Correct 553 ms 1060 KB Output is correct
4 Correct 673 ms 27648 KB Output is correct
5 Correct 663 ms 24524 KB Output is correct
6 Correct 80 ms 528 KB Output is correct
7 Correct 663 ms 24472 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 948 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 427 ms 872 KB Output is correct
4 Correct 444 ms 964 KB Output is correct
5 Correct 548 ms 964 KB Output is correct
6 Correct 443 ms 1000 KB Output is correct
7 Correct 463 ms 964 KB Output is correct
8 Correct 439 ms 892 KB Output is correct
9 Correct 473 ms 956 KB Output is correct
10 Correct 427 ms 984 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 704 KB Output is correct
2 Correct 151 ms 684 KB Output is correct
3 Correct 351 ms 13260 KB Output is correct
4 Correct 266 ms 724 KB Output is correct
5 Correct 259 ms 9948 KB Output is correct
6 Correct 174 ms 708 KB Output is correct
7 Correct 276 ms 736 KB Output is correct
8 Correct 262 ms 656 KB Output is correct
9 Correct 273 ms 18224 KB Output is correct
10 Correct 357 ms 18164 KB Output is correct
11 Correct 370 ms 35736 KB Output is correct
12 Correct 325 ms 30912 KB Output is correct
13 Correct 246 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 704 KB Output is correct
2 Correct 151 ms 684 KB Output is correct
3 Correct 351 ms 13260 KB Output is correct
4 Correct 266 ms 724 KB Output is correct
5 Correct 259 ms 9948 KB Output is correct
6 Correct 174 ms 708 KB Output is correct
7 Correct 276 ms 736 KB Output is correct
8 Correct 262 ms 656 KB Output is correct
9 Correct 273 ms 18224 KB Output is correct
10 Correct 357 ms 18164 KB Output is correct
11 Correct 370 ms 35736 KB Output is correct
12 Correct 325 ms 30912 KB Output is correct
13 Correct 246 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 212 ms 656 KB Output is correct
16 Correct 294 ms 656 KB Output is correct
17 Correct 227 ms 744 KB Output is correct
18 Correct 296 ms 10000 KB Output is correct
19 Correct 318 ms 752 KB Output is correct
20 Correct 350 ms 10284 KB Output is correct
21 Correct 272 ms 904 KB Output is correct
22 Correct 315 ms 764 KB Output is correct
23 Correct 364 ms 22036 KB Output is correct
24 Correct 360 ms 22104 KB Output is correct
25 Correct 578 ms 43852 KB Output is correct
26 Correct 448 ms 36756 KB Output is correct
27 Correct 237 ms 912 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 704 KB Output is correct
2 Correct 151 ms 684 KB Output is correct
3 Correct 351 ms 13260 KB Output is correct
4 Correct 266 ms 724 KB Output is correct
5 Correct 259 ms 9948 KB Output is correct
6 Correct 174 ms 708 KB Output is correct
7 Correct 276 ms 736 KB Output is correct
8 Correct 262 ms 656 KB Output is correct
9 Correct 273 ms 18224 KB Output is correct
10 Correct 357 ms 18164 KB Output is correct
11 Correct 370 ms 35736 KB Output is correct
12 Correct 325 ms 30912 KB Output is correct
13 Correct 246 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 212 ms 656 KB Output is correct
16 Correct 294 ms 656 KB Output is correct
17 Correct 227 ms 744 KB Output is correct
18 Correct 296 ms 10000 KB Output is correct
19 Correct 318 ms 752 KB Output is correct
20 Correct 350 ms 10284 KB Output is correct
21 Correct 272 ms 904 KB Output is correct
22 Correct 315 ms 764 KB Output is correct
23 Correct 364 ms 22036 KB Output is correct
24 Correct 360 ms 22104 KB Output is correct
25 Correct 578 ms 43852 KB Output is correct
26 Correct 448 ms 36756 KB Output is correct
27 Correct 237 ms 912 KB Output is correct
28 Correct 384 ms 656 KB Output is correct
29 Correct 296 ms 840 KB Output is correct
30 Correct 508 ms 24096 KB Output is correct
31 Correct 350 ms 832 KB Output is correct
32 Correct 432 ms 21144 KB Output is correct
33 Correct 554 ms 1032 KB Output is correct
34 Correct 367 ms 936 KB Output is correct
35 Correct 316 ms 892 KB Output is correct
36 Correct 508 ms 24732 KB Output is correct
37 Correct 368 ms 24736 KB Output is correct
38 Correct 626 ms 48824 KB Output is correct
39 Correct 592 ms 44400 KB Output is correct
40 Correct 356 ms 972 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 988 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 468 ms 884 KB Output is correct
4 Correct 569 ms 10172 KB Output is correct
5 Correct 34 ms 656 KB Output is correct
6 Correct 494 ms 2340 KB Output is correct
7 Correct 1 ms 400 KB Output is correct
8 Correct 414 ms 976 KB Output is correct
9 Correct 553 ms 1060 KB Output is correct
10 Correct 673 ms 27648 KB Output is correct
11 Correct 663 ms 24524 KB Output is correct
12 Correct 80 ms 528 KB Output is correct
13 Correct 663 ms 24472 KB Output is correct
14 Correct 503 ms 948 KB Output is correct
15 Correct 0 ms 400 KB Output is correct
16 Correct 427 ms 872 KB Output is correct
17 Correct 444 ms 964 KB Output is correct
18 Correct 548 ms 964 KB Output is correct
19 Correct 443 ms 1000 KB Output is correct
20 Correct 463 ms 964 KB Output is correct
21 Correct 439 ms 892 KB Output is correct
22 Correct 473 ms 956 KB Output is correct
23 Correct 427 ms 984 KB Output is correct
24 Correct 196 ms 704 KB Output is correct
25 Correct 151 ms 684 KB Output is correct
26 Correct 351 ms 13260 KB Output is correct
27 Correct 266 ms 724 KB Output is correct
28 Correct 259 ms 9948 KB Output is correct
29 Correct 174 ms 708 KB Output is correct
30 Correct 276 ms 736 KB Output is correct
31 Correct 262 ms 656 KB Output is correct
32 Correct 273 ms 18224 KB Output is correct
33 Correct 357 ms 18164 KB Output is correct
34 Correct 370 ms 35736 KB Output is correct
35 Correct 325 ms 30912 KB Output is correct
36 Correct 246 ms 656 KB Output is correct
37 Correct 0 ms 400 KB Output is correct
38 Correct 212 ms 656 KB Output is correct
39 Correct 294 ms 656 KB Output is correct
40 Correct 227 ms 744 KB Output is correct
41 Correct 296 ms 10000 KB Output is correct
42 Correct 318 ms 752 KB Output is correct
43 Correct 350 ms 10284 KB Output is correct
44 Correct 272 ms 904 KB Output is correct
45 Correct 315 ms 764 KB Output is correct
46 Correct 364 ms 22036 KB Output is correct
47 Correct 360 ms 22104 KB Output is correct
48 Correct 578 ms 43852 KB Output is correct
49 Correct 448 ms 36756 KB Output is correct
50 Correct 237 ms 912 KB Output is correct
51 Correct 384 ms 656 KB Output is correct
52 Correct 296 ms 840 KB Output is correct
53 Correct 508 ms 24096 KB Output is correct
54 Correct 350 ms 832 KB Output is correct
55 Correct 432 ms 21144 KB Output is correct
56 Correct 554 ms 1032 KB Output is correct
57 Correct 367 ms 936 KB Output is correct
58 Correct 316 ms 892 KB Output is correct
59 Correct 508 ms 24732 KB Output is correct
60 Correct 368 ms 24736 KB Output is correct
61 Correct 626 ms 48824 KB Output is correct
62 Correct 592 ms 44400 KB Output is correct
63 Correct 356 ms 972 KB Output is correct
64 Correct 835 ms 1172 KB Output is correct
65 Correct 548 ms 26560 KB Output is correct
66 Correct 534 ms 23400 KB Output is correct
67 Correct 387 ms 1124 KB Output is correct
68 Correct 504 ms 1168 KB Output is correct
69 Correct 829 ms 48032 KB Output is correct
70 Correct 687 ms 39752 KB Output is correct
71 Correct 451 ms 5156 KB Output is correct
72 Correct 541 ms 1264 KB Output is correct