oj.uz

Submission #708220

# Submission time Handle Problem Language Result Execution time Memory
708220 2023-03-11T10:27:14 Z esomer Two Transportations (JOI19_transportations) C++17
0 / 100
 3000 ms 35880 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);
	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);
	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 410 ms 972 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 566 ms 968 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 211 ms 708 KB Output is correct
2 Correct 132 ms 676 KB Output is correct
3 Correct 318 ms 13344 KB Output is correct
4 Correct 330 ms 656 KB Output is correct
5 Correct 320 ms 9980 KB Output is correct
6 Correct 261 ms 656 KB Output is correct
7 Correct 226 ms 656 KB Output is correct
8 Correct 247 ms 656 KB Output is correct
9 Correct 296 ms 18108 KB Output is correct
10 Correct 340 ms 18116 KB Output is correct
11 Correct 456 ms 35880 KB Output is correct
12 Correct 444 ms 30828 KB Output is correct
13 Correct 186 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 211 ms 708 KB Output is correct
2 Correct 132 ms 676 KB Output is correct
3 Correct 318 ms 13344 KB Output is correct
4 Correct 330 ms 656 KB Output is correct
5 Correct 320 ms 9980 KB Output is correct
6 Correct 261 ms 656 KB Output is correct
7 Correct 226 ms 656 KB Output is correct
8 Correct 247 ms 656 KB Output is correct
9 Correct 296 ms 18108 KB Output is correct
10 Correct 340 ms 18116 KB Output is correct
11 Correct 456 ms 35880 KB Output is correct
12 Correct 444 ms 30828 KB Output is correct
13 Correct 186 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 211 ms 708 KB Output is correct
2 Correct 132 ms 676 KB Output is correct
3 Correct 318 ms 13344 KB Output is correct
4 Correct 330 ms 656 KB Output is correct
5 Correct 320 ms 9980 KB Output is correct
6 Correct 261 ms 656 KB Output is correct
7 Correct 226 ms 656 KB Output is correct
8 Correct 247 ms 656 KB Output is correct
9 Correct 296 ms 18108 KB Output is correct
10 Correct 340 ms 18116 KB Output is correct
11 Correct 456 ms 35880 KB Output is correct
12 Correct 444 ms 30828 KB Output is correct
13 Correct 186 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 410 ms 972 KB Output is correct
2 Execution timed out 3000 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -