oj.uz

Submission #767305

# Submission time Handle Problem Language Result Execution time Memory
767305 2023-06-26T15:23:30 Z minhcool Two Transportations (JOI19_transportations) C++17
6 / 100
 552 ms 27316 KB 
#include "Azer.h"
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e9 + 7, mod = 1e9 + 7;

//mt19937 rng(1);

/*
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}*/

/*
Algo: 
N times: A gives B the value (x - lst) (lst = last value)
         B gives A the value (y - lst)
if(x < y) -> A give info to B, else B give info to A
Just like that.
*/

int n;
vector<ii> Adj[N];
vector<iii> edges;

priority_queue<ii, vector<ii>, greater<ii>> pq1;

void send1(int x, int bits){
	for(int i = 0; i < bits; i++){
		SendA((x & (1LL << (bits - i - 1))) != 0);
	}
}

int answer[N];
bool done[N];

int phase, rem;
int lst, pls, node;
int a = 0, b = 0;

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
	n = N;
	for(int i = 1; i < n; i++) answer[i] = oo;
  	for(int i = 0; i < A; i++){
  		Adj[U[i]].pb({V[i], C[i]});
		Adj[V[i]].pb({U[i], C[i]});	
		//edges.pb({{U[i], V[i]}, C[i]});
	}
	for(auto it : Adj[0]){
		int v = it.fi, w = it.se;
		if(answer[v] > answer[b] + w){
			answer[v] = answer[b] + w;
			pq1.push({answer[v], v});
		}
	}
	phase = 0, rem = 9;
	pls = 511, node = 2047;
	while(!pq1.empty()){
		int u = pq1.top().se, d = pq1.top().fi;
		if(done[u]){
			pq1.pop();
			continue;
		}
		//send1(d - lst, 9);
		pls = d - lst;
		node = u;
		break;
	}
	done[0] = 1;
	send1(pls, 9);
}

void ReceiveA(bool x) {
//	cout << phase << " " << rem << "\n";
	rem--;
	if(!phase) a = a * 2 + x;
	else b = b * 2 + x;
	if(rem) return;
	if(!phase){
	//	cout << "COMPARING " << a << " " << pls << "\n";
		if(pls < a){
			send1(node, 11); 
		}
		else{
			//a = pls;
			phase = 1;
			rem = 11;
			return;
		}
	}
//	cout << "OK\n";
	if(a > pls) b = node;
	a = min(a, pls);
	answer[b] = a + lst;
	lst += a;
	//cout << "DONE " << b << "\n";
	done[b] = 1;
	for(auto it : Adj[b]){
		int v = it.fi, w = it.se;
		if(answer[v] > answer[b] + w){
			answer[v] = answer[b] + w;
			pq1.push({answer[v], v});
		}
	}
	bool ck = 0;
	for(int i = 0; i < n; i++) ck |= (!done[i]);
	if(!ck) return;
//	lst = a;
	a = b = 0;		
	phase = 0, rem = 9;
	pls = 511, node = 2047;
	while(!pq1.empty()){
		int u = pq1.top().se, d = pq1.top().fi;
		if(done[u]){
			pq1.pop();
			continue;
		}
		//send1(d - lst, 9);
		pls = d - lst;
		phase = 0;
		rem = 9;
		node = u;
		break;
	}
//	if(pq1.empty() && pls == 511) return;
//	cout << "CAN A " << lst << " " << node << " " << pls << "\n";
	send1(pls, 9);
}

vector<int> Answer() {
	vector<int> v;
	for(int i = 0; i < n; i++) v.pb(answer[i]);
	return v;
}
#include "Baijan.h"
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e9 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n2;
vector<ii> Adj2[N];


priority_queue<ii, vector<ii>, greater<ii>> pq2;

int answer2[N], done2[N];

int aa = 0, bb = 0;
// lst length, phase 0/1, remmaining bits until done, minimum node, minimum dist - lst length
int lstt, phasee, remm, nodee, plss;

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	n2 = N;
	for(int i = 1; i < N; i++) answer2[i] = oo;
	for(int i = 0; i < B; i++){
		Adj2[S[i]].pb({T[i], D[i]});
		Adj2[T[i]].pb({S[i], D[i]});
	}
	for(auto it : Adj2[0]){
		int v = it.fi, w = it.se;
		if(answer2[v] > answer2[0] + w){
			answer2[v] = answer2[0] + w;
			pq2.push({answer2[v], v});
		}
	}
	done2[0] = 1;
	lstt = 0, phasee = 0, remm = 9, nodee = (pq2.empty() ? 2047 : pq2.top().se), plss = (pq2.empty() ? 511 : pq2.top().fi);
}

//bool done2[N];

void send2(int x, int bits){
//	cout << "SEND " << x << "\n";
	for(int i = 0; i < bits; i++){
		SendB((x & (1LL << (bits - i - 1))) != 0);
	}
}

void ReceiveB(bool y) {
	remm--;
	if(!phasee) aa = aa * 2 + y;
	else bb = bb * 2 + y;
	if(remm) return;
	if(!phasee){
	//	cout << "COMPARING " << aa << " " << plss << "\n";
		send2(plss, 9);
		if(plss <= aa){
			send2(nodee, 11);
			phasee = 0, remm = 9;
		}
		else{
			phasee = 1, remm = 11;
			return;
		}
	}
	if(plss <= aa) bb = nodee;
	aa = min(aa, plss);
	lstt += aa;
	answer2[bb] = lstt;
	done2[bb] = 1;
	for(auto it : Adj2[bb]){
		int v = it.fi, w = it.se;
		if(answer2[v] > answer2[bb] + w){
			answer2[v] = answer2[bb] + w;
			pq2.push({answer2[v], v});
		}
	}
//	lstt = 
	aa = bb = 0;
	phasee = 0;
	plss = 511, nodee = 2047;
	while(!pq2.empty()){
		int u = pq2.top().se, d = pq2.top().fi;
	//	pq2.pop();
		if(done2[u]){
			pq2.pop();	
			continue;
		}
		//send1(d - lst, 9);
		plss = d - lstt;
		phasee = 0;
		remm = 9;
		nodee = u;
		break;
	}
//	cout << "CAN B " << lstt << " " << nodee << " " << plss << "\n";
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 14828 KB Output is correct
2 Correct 8 ms 14700 KB Output is correct
3 Correct 403 ms 14832 KB Output is correct
4 Correct 552 ms 24116 KB Output is correct
5 Correct 32 ms 14736 KB Output is correct
6 Correct 462 ms 16248 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14480 KB Output is correct
2 Correct 461 ms 14888 KB Output is correct
3 Incorrect 12 ms 14848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 14840 KB Output is correct
2 Correct 7 ms 14480 KB Output is correct
3 Correct 395 ms 14812 KB Output is correct
4 Correct 496 ms 14796 KB Output is correct
5 Correct 390 ms 14800 KB Output is correct
6 Incorrect 8 ms 14796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 14736 KB Output is correct
2 Correct 201 ms 14708 KB Output is correct
3 Correct 253 ms 27316 KB Output is correct
4 Correct 186 ms 14736 KB Output is correct
5 Correct 211 ms 24124 KB Output is correct
6 Correct 186 ms 14744 KB Output is correct
7 Incorrect 28 ms 14772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 14736 KB Output is correct
2 Correct 201 ms 14708 KB Output is correct
3 Correct 253 ms 27316 KB Output is correct
4 Correct 186 ms 14736 KB Output is correct
5 Correct 211 ms 24124 KB Output is correct
6 Correct 186 ms 14744 KB Output is correct
7 Incorrect 28 ms 14772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 14736 KB Output is correct
2 Correct 201 ms 14708 KB Output is correct
3 Correct 253 ms 27316 KB Output is correct
4 Correct 186 ms 14736 KB Output is correct
5 Correct 211 ms 24124 KB Output is correct
6 Correct 186 ms 14744 KB Output is correct
7 Incorrect 28 ms 14772 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 14828 KB Output is correct
2 Correct 8 ms 14700 KB Output is correct
3 Correct 403 ms 14832 KB Output is correct
4 Correct 552 ms 24116 KB Output is correct
5 Correct 32 ms 14736 KB Output is correct
6 Correct 462 ms 16248 KB Output is correct
7 Correct 6 ms 14480 KB Output is correct
8 Correct 461 ms 14888 KB Output is correct
9 Incorrect 12 ms 14848 KB Output isn't correct
10 Halted 0 ms 0 KB -