oj.uz

Submission #708215

# Submission time Handle Problem Language Result Execution time Memory
708215 2023-03-11T10:21:08 Z esomer Two Transportations (JOI19_transportations) C++17
0 / 100
 3000 ms 35876 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 node){
	int n = (int)dist.size();
	priority_queue<pair<int, int>> q; q.push({-dist[node], node});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != node) 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);
	for(int i = 1; i < n; i++){
		if(dist[i] == 1e9) s.insert({1e9, i});
	}
	//~ cout << "Dist" << endl;
	//~ for(int x : dist) cout << x << " "; cout << endl;
	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 node){
	int n = (int)distB.size();
	priority_queue<pair<int, int>> q; q.push({-distB[node], node});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != node) 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);
	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 980 KB Output is correct
2 Execution timed out 3000 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 944 KB Output is correct
2 Execution timed out 3000 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 692 KB Output is correct
2 Correct 239 ms 680 KB Output is correct
3 Correct 342 ms 13384 KB Output is correct
4 Correct 329 ms 656 KB Output is correct
5 Correct 309 ms 10012 KB Output is correct
6 Correct 268 ms 656 KB Output is correct
7 Correct 138 ms 784 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 300 ms 18200 KB Output is correct
10 Correct 382 ms 18192 KB Output is correct
11 Correct 470 ms 35876 KB Output is correct
12 Correct 389 ms 30900 KB Output is correct
13 Correct 244 ms 656 KB Output is correct
14 Execution timed out 3000 ms 200 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 692 KB Output is correct
2 Correct 239 ms 680 KB Output is correct
3 Correct 342 ms 13384 KB Output is correct
4 Correct 329 ms 656 KB Output is correct
5 Correct 309 ms 10012 KB Output is correct
6 Correct 268 ms 656 KB Output is correct
7 Correct 138 ms 784 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 300 ms 18200 KB Output is correct
10 Correct 382 ms 18192 KB Output is correct
11 Correct 470 ms 35876 KB Output is correct
12 Correct 389 ms 30900 KB Output is correct
13 Correct 244 ms 656 KB Output is correct
14 Execution timed out 3000 ms 200 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 692 KB Output is correct
2 Correct 239 ms 680 KB Output is correct
3 Correct 342 ms 13384 KB Output is correct
4 Correct 329 ms 656 KB Output is correct
5 Correct 309 ms 10012 KB Output is correct
6 Correct 268 ms 656 KB Output is correct
7 Correct 138 ms 784 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 300 ms 18200 KB Output is correct
10 Correct 382 ms 18192 KB Output is correct
11 Correct 470 ms 35876 KB Output is correct
12 Correct 389 ms 30900 KB Output is correct
13 Correct 244 ms 656 KB Output is correct
14 Execution timed out 3000 ms 200 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 980 KB Output is correct
2 Execution timed out 3000 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -