oj.uz

Submission #831553

# Submission time Handle Problem Language Result Execution time Memory
831553 2023-08-20T10:20:16 Z NoName14159 Two Transportations (JOI19_transportations) C++17
68 / 100
 575 ms 49412 KB 
#include "Azer.h"
#include <stdlib.h>
#include <cassert>
#include <queue>
#define MAXN 2007
#define MAXM 500007
#define vi std::vector<int>
#define pii std::pair<int,int>
#define vpii std::vector<pii>
#define pqpii std::priority_queue<pii,vpii,std::greater<pii>>
#define LOOP(I,X) for(int I=0;I<X;I++)
#define pub push_back
namespace{
	enum Mode{
		CL, // choose leader
		RE, // recommend edge
		DW, // determine winner
		SR, // send relax
		RX  // relax
	};
	Mode mode;
	bool leader;
	bool winner;
	int n;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool buf[58007];
	int buf_size=0;
	int buf_now=0;
	int t=0;
	int bits_next;
int cnt=0;
	int Read(int bits){
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=(int)buf[buf_now+i];
		}
		buf_now+=bits;
		return ans;
	}
	void Send(int bits,int x){
		LOOP(i,bits){
cnt++;
assert(buf_size+cnt<=58000);
			SendA((bool)((x>>(bits-1-i))&1));
		}
	}
	void Do(){
		while(t<n-1){
			if(mode==CL){
				mode=RE;
				if(leader){
					bool new_leader=true;//(bool)(std::rand()%2);
					Send(1,(int)new_leader);
					if(new_leader){
						leader=!leader;
					}
				}else{
					bool new_leader=(bool)Read(1);
					if(new_leader){
						leader=!leader;
					}
				}
				if(leader){
					bits_next=9;
					return;
				}
			}
			if(mode==RE){
				mode=DW;
				while(!pq.empty()){
					pii x=pq.top();
					if(!visited[x.second]){
						break;
					}
					pq.pop();
				}
				if(pq.empty()){
					rec={511,-1};
				}else{
					rec=pq.top();
					rec.first-=relax_w;
				}
				if(leader){
					rec_other=Read(9);
				}else{
					Send(9,rec.first);
					bits_next=1;
					return;
				}
			}
			if(mode==DW){
				mode=SR;
				if(leader){
					if(rec.first<=rec_other){
						Send(1,1);
						winner=true;
					}else{
						Send(1,0);
						winner=false;
					}
				}else{
					winner=!(bool)Read(1);
				}
				if(!winner){
					if(leader){
						bits_next=11;
					}else{
						bits_next=20;
					}
					return;
				}
			}
			if(mode==SR){
				mode=RX;
				if(leader){
					if(winner){
						Send(11,rec.second);
						relax_v=rec.second;
						Send(9,rec.first);
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=rec_other;
					}
				}else{
					if(winner){
						Send(11,rec.second);
						relax_v=rec.second;
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=Read(9);
					}
				}
			}
			if(mode==RX){
				mode=CL;
				dis[relax_v]=relax_w;
				visited[relax_v]=true;
				for(pii x:e[relax_v]){
					if(!visited[x.first]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				t++;
				if(!leader){
					bits_next=1;
					return;
				}
			}
		}
	}
}
void InitA(int N,int A,vi U,vi V,vi C){
	//std::srand(49);
	n=N;
	LOOP(i,A){
		e[U[i]].pub({V[i],C[i]});
		e[V[i]].pub({U[i],C[i]});
	}
	dis[0]=0;
	visited[0]=true;
	for(pii x:e[0]){
		pq.push({x.second,x.first});
	}
	mode=CL;
	leader=true;
	Do();
}
void ReceiveA(bool x){
	buf[buf_size]=x;
	buf_size++;
	if(buf_size-buf_now==bits_next){
		Do();
	}
}
vi Answer(){
	vi ans;
	LOOP(i,n){
		ans.pub(dis[i]);
	}
	return ans;
}

#include "Baijan.h"
#include <stdlib.h>
#include <cassert>
#include <queue>
#define MAXN 2007
#define MAXM 500007
#define vi std::vector<int>
#define pii std::pair<int,int>
#define vpii std::vector<pii>
#define pqpii std::priority_queue<pii,vpii,std::greater<pii>>
#define LOOP(I,X) for(int I=0;I<X;I++)
#define pub push_back
namespace{
	enum Mode{
		CL, // choose leader
		RE, // recommend edge
		DW, // determine winner
		SR, // send relax
		RX  // relax
	};
	Mode mode;
	bool leader;
	bool winner;
	int n;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool buf[58007];
	int buf_size=0;
	int buf_now=0;
	int t=0;
	int bits_next;
int cnt=0;
	int Read(int bits){
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=(int)buf[buf_now+i];
		}
		buf_now+=bits;
		return ans;
	}
	void Send(int bits,int x){
		LOOP(i,bits){
cnt++;
assert(buf_size+cnt<=58000);
			SendB((bool)((x>>(bits-1-i))&1));
		}
	}
	void Do(){
		while(t<n-1){
			if(mode==CL){
				mode=RE;
				if(leader){
					bool new_leader=true;//(bool)(std::rand()%2);
					Send(1,(int)new_leader);
					if(new_leader){
						leader=!leader;
					}
				}else{
					bool new_leader=(bool)Read(1);
					if(new_leader){
						leader=!leader;
					}
				}
				if(leader){
					bits_next=9;
					return;
				}
			}
			if(mode==RE){
				mode=DW;
				while(!pq.empty()){
					pii x=pq.top();
					if(!visited[x.second]){
						break;
					}
					pq.pop();
				}
				if(pq.empty()){
					rec={511,-1};
				}else{
					rec=pq.top();
					rec.first-=relax_w;
				}
				if(leader){
					rec_other=Read(9);
				}else{
					Send(9,rec.first);
					bits_next=1;
					return;
				}
			}
			if(mode==DW){
				mode=SR;
				if(leader){
					if(rec.first<=rec_other){
						Send(1,1);
						winner=true;
					}else{
						Send(1,0);
						winner=false;
					}
				}else{
					winner=!(bool)Read(1);
				}
				if(!winner){
					if(leader){
						bits_next=11;
					}else{
						bits_next=20;
					}
					return;
				}
			}
			if(mode==SR){
				mode=RX;
				if(leader){
					if(winner){
						Send(11,rec.second);
						relax_v=rec.second;
						Send(9,rec.first);
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=rec_other;
					}
				}else{
					if(winner){
						Send(11,rec.second);
						relax_v=rec.second;
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=Read(9);
					}
				}
			}
			if(mode==RX){
				mode=CL;
				dis[relax_v]=relax_w;
				visited[relax_v]=true;
				for(pii x:e[relax_v]){
					if(!visited[x.first]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				t++;
				if(!leader){
					bits_next=1;
					return;
				}
			}
		}
	}
}
void InitB(int N,int A,vi U,vi V,vi C){
	//std::srand(49);
	n=N;
	LOOP(i,A){
		e[U[i]].pub({V[i],C[i]});
		e[V[i]].pub({U[i],C[i]});
	}
	dis[0]=0;
	visited[0]=true;
	for(pii x:e[0]){
		pq.push({x.second,x.first});
	}
	mode=CL;
	leader=false;
	bits_next=1;
}
void ReceiveB(bool x){
	buf[buf_size]=x;
	buf_size++;
	if(buf_size-buf_now==bits_next){
		Do();
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 904 KB Output is correct
2 Correct 0 ms 712 KB Output is correct
3 Correct 420 ms 864 KB Output is correct
4 Correct 391 ms 10136 KB Output is correct
5 Correct 20 ms 980 KB Output is correct
6 Correct 263 ms 2368 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 712 KB Output is correct
2 Runtime error 264 ms 444 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 824 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 360 ms 792 KB Output is correct
4 Runtime error 199 ms 428 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 744 KB Output is correct
2 Correct 190 ms 752 KB Output is correct
3 Correct 308 ms 13316 KB Output is correct
4 Correct 155 ms 808 KB Output is correct
5 Correct 270 ms 10036 KB Output is correct
6 Correct 179 ms 752 KB Output is correct
7 Correct 138 ms 984 KB Output is correct
8 Correct 161 ms 800 KB Output is correct
9 Correct 278 ms 19524 KB Output is correct
10 Correct 205 ms 19616 KB Output is correct
11 Correct 469 ms 38244 KB Output is correct
12 Correct 346 ms 35960 KB Output is correct
13 Correct 189 ms 840 KB Output is correct
14 Correct 1 ms 656 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 744 KB Output is correct
2 Correct 190 ms 752 KB Output is correct
3 Correct 308 ms 13316 KB Output is correct
4 Correct 155 ms 808 KB Output is correct
5 Correct 270 ms 10036 KB Output is correct
6 Correct 179 ms 752 KB Output is correct
7 Correct 138 ms 984 KB Output is correct
8 Correct 161 ms 800 KB Output is correct
9 Correct 278 ms 19524 KB Output is correct
10 Correct 205 ms 19616 KB Output is correct
11 Correct 469 ms 38244 KB Output is correct
12 Correct 346 ms 35960 KB Output is correct
13 Correct 189 ms 840 KB Output is correct
14 Correct 1 ms 656 KB Output is correct
15 Correct 215 ms 732 KB Output is correct
16 Correct 203 ms 736 KB Output is correct
17 Correct 188 ms 780 KB Output is correct
18 Correct 301 ms 10120 KB Output is correct
19 Correct 283 ms 780 KB Output is correct
20 Correct 292 ms 10268 KB Output is correct
21 Correct 232 ms 840 KB Output is correct
22 Correct 193 ms 832 KB Output is correct
23 Correct 337 ms 22652 KB Output is correct
24 Correct 424 ms 22664 KB Output is correct
25 Correct 546 ms 44128 KB Output is correct
26 Correct 492 ms 40616 KB Output is correct
27 Correct 270 ms 920 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 744 KB Output is correct
2 Correct 190 ms 752 KB Output is correct
3 Correct 308 ms 13316 KB Output is correct
4 Correct 155 ms 808 KB Output is correct
5 Correct 270 ms 10036 KB Output is correct
6 Correct 179 ms 752 KB Output is correct
7 Correct 138 ms 984 KB Output is correct
8 Correct 161 ms 800 KB Output is correct
9 Correct 278 ms 19524 KB Output is correct
10 Correct 205 ms 19616 KB Output is correct
11 Correct 469 ms 38244 KB Output is correct
12 Correct 346 ms 35960 KB Output is correct
13 Correct 189 ms 840 KB Output is correct
14 Correct 1 ms 656 KB Output is correct
15 Correct 215 ms 732 KB Output is correct
16 Correct 203 ms 736 KB Output is correct
17 Correct 188 ms 780 KB Output is correct
18 Correct 301 ms 10120 KB Output is correct
19 Correct 283 ms 780 KB Output is correct
20 Correct 292 ms 10268 KB Output is correct
21 Correct 232 ms 840 KB Output is correct
22 Correct 193 ms 832 KB Output is correct
23 Correct 337 ms 22652 KB Output is correct
24 Correct 424 ms 22664 KB Output is correct
25 Correct 546 ms 44128 KB Output is correct
26 Correct 492 ms 40616 KB Output is correct
27 Correct 270 ms 920 KB Output is correct
28 Correct 259 ms 772 KB Output is correct
29 Correct 282 ms 748 KB Output is correct
30 Correct 471 ms 24160 KB Output is correct
31 Correct 260 ms 740 KB Output is correct
32 Correct 512 ms 21156 KB Output is correct
33 Correct 249 ms 876 KB Output is correct
34 Correct 179 ms 996 KB Output is correct
35 Correct 187 ms 872 KB Output is correct
36 Correct 429 ms 25120 KB Output is correct
37 Correct 371 ms 25216 KB Output is correct
38 Correct 575 ms 49412 KB Output is correct
39 Correct 530 ms 46944 KB Output is correct
40 Correct 243 ms 964 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 904 KB Output is correct
2 Correct 0 ms 712 KB Output is correct
3 Correct 420 ms 864 KB Output is correct
4 Correct 391 ms 10136 KB Output is correct
5 Correct 20 ms 980 KB Output is correct
6 Correct 263 ms 2368 KB Output is correct
7 Correct 0 ms 712 KB Output is correct
8 Runtime error 264 ms 444 KB Execution killed with signal 13
9 Halted 0 ms 0 KB -