oj.uz

답안 #708213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708213 2023-03-11T10:11:48 Z esomer Two Transportations (JOI19_transportations) C++17
0 / 100
 3000 ms 972 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);
			//~ cout << "DistA" << endl;
			//~ for(int x : dist) cout << x << " "; cout << endl;
			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().
		//~ cout << "A mine " << mine << " his " << his << endl;
		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);
	//~ cout << "DistB" << endl;
	//~ for(int x : distB) cout << x << " "; cout << endl;
}

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;
			//~ cout << "DistB" << endl;
			//~ for(int x : distB) cout << x << " "; cout << endl;
		}
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 438 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3000 ms 200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 179 ms 492 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 656 KB Output is correct
2 Runtime error 148 ms 348 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 656 KB Output is correct
2 Runtime error 148 ms 348 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 656 KB Output is correct
2 Runtime error 148 ms 348 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 438 ms 972 KB Output is correct
2 Execution timed out 3000 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -