oj.uz

Submission #831141

# Submission time Handle Problem Language Result Execution time Memory
831141 2023-08-19T19:31:11 Z NoName14159 Two Transportations (JOI19_transportations) C++17
84 / 100
 589 ms 49596 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;
	bool *visited;
	vpii *e;
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool *buf;
	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=(bool)(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){
	dis=(int *)malloc(sizeof(int)*MAXN);
	visited=(bool *)malloc(sizeof(bool)*MAXN);
	LOOP(i,MAXN){
		visited[i]=false;
	}
	e=(vpii *)malloc(sizeof(vpii)*MAXN);
	buf=(bool *)malloc(sizeof(bool)*58007);
	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;
	bool *visited;
	vpii *e;
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool *buf;
	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=(bool)(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){
	dis=(int *)malloc(sizeof(int)*MAXN);
	visited=(bool *)malloc(sizeof(bool)*MAXN);
	LOOP(i,MAXN){
		visited[i]=false;
	}
	e=(vpii *)malloc(sizeof(vpii)*MAXN);
	buf=(bool *)malloc(sizeof(bool)*58007);
	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 380 ms 872 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 437 ms 884 KB Output is correct
4 Correct 459 ms 10112 KB Output is correct
5 Correct 15 ms 756 KB Output is correct
6 Correct 416 ms 2408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 400 KB Output is correct
2 Correct 255 ms 852 KB Output is correct
3 Correct 353 ms 1120 KB Output is correct
4 Correct 589 ms 27904 KB Output is correct
5 Correct 478 ms 24496 KB Output is correct
6 Correct 60 ms 632 KB Output is correct
7 Correct 385 ms 24772 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 832 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 370 ms 856 KB Output is correct
4 Correct 334 ms 892 KB Output is correct
5 Correct 297 ms 856 KB Output is correct
6 Correct 391 ms 828 KB Output is correct
7 Correct 299 ms 828 KB Output is correct
8 Correct 347 ms 808 KB Output is correct
9 Correct 285 ms 780 KB Output is correct
10 Correct 360 ms 804 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 728 KB Output is correct
2 Correct 165 ms 832 KB Output is correct
3 Correct 260 ms 13264 KB Output is correct
4 Correct 144 ms 716 KB Output is correct
5 Correct 199 ms 9916 KB Output is correct
6 Correct 175 ms 692 KB Output is correct
7 Correct 127 ms 752 KB Output is correct
8 Correct 181 ms 756 KB Output is correct
9 Correct 284 ms 19440 KB Output is correct
10 Correct 245 ms 19500 KB Output is correct
11 Correct 416 ms 38292 KB Output is correct
12 Correct 334 ms 35956 KB Output is correct
13 Correct 155 ms 728 KB Output is correct
14 Correct 0 ms 400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 728 KB Output is correct
2 Correct 165 ms 832 KB Output is correct
3 Correct 260 ms 13264 KB Output is correct
4 Correct 144 ms 716 KB Output is correct
5 Correct 199 ms 9916 KB Output is correct
6 Correct 175 ms 692 KB Output is correct
7 Correct 127 ms 752 KB Output is correct
8 Correct 181 ms 756 KB Output is correct
9 Correct 284 ms 19440 KB Output is correct
10 Correct 245 ms 19500 KB Output is correct
11 Correct 416 ms 38292 KB Output is correct
12 Correct 334 ms 35956 KB Output is correct
13 Correct 155 ms 728 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 205 ms 708 KB Output is correct
16 Correct 143 ms 688 KB Output is correct
17 Correct 209 ms 776 KB Output is correct
18 Correct 310 ms 10008 KB Output is correct
19 Correct 235 ms 836 KB Output is correct
20 Correct 269 ms 10236 KB Output is correct
21 Correct 228 ms 872 KB Output is correct
22 Correct 231 ms 800 KB Output is correct
23 Correct 281 ms 22556 KB Output is correct
24 Correct 271 ms 22328 KB Output is correct
25 Correct 497 ms 44256 KB Output is correct
26 Correct 446 ms 40688 KB Output is correct
27 Correct 165 ms 1104 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 728 KB Output is correct
2 Correct 165 ms 832 KB Output is correct
3 Correct 260 ms 13264 KB Output is correct
4 Correct 144 ms 716 KB Output is correct
5 Correct 199 ms 9916 KB Output is correct
6 Correct 175 ms 692 KB Output is correct
7 Correct 127 ms 752 KB Output is correct
8 Correct 181 ms 756 KB Output is correct
9 Correct 284 ms 19440 KB Output is correct
10 Correct 245 ms 19500 KB Output is correct
11 Correct 416 ms 38292 KB Output is correct
12 Correct 334 ms 35956 KB Output is correct
13 Correct 155 ms 728 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 205 ms 708 KB Output is correct
16 Correct 143 ms 688 KB Output is correct
17 Correct 209 ms 776 KB Output is correct
18 Correct 310 ms 10008 KB Output is correct
19 Correct 235 ms 836 KB Output is correct
20 Correct 269 ms 10236 KB Output is correct
21 Correct 228 ms 872 KB Output is correct
22 Correct 231 ms 800 KB Output is correct
23 Correct 281 ms 22556 KB Output is correct
24 Correct 271 ms 22328 KB Output is correct
25 Correct 497 ms 44256 KB Output is correct
26 Correct 446 ms 40688 KB Output is correct
27 Correct 165 ms 1104 KB Output is correct
28 Correct 199 ms 756 KB Output is correct
29 Correct 217 ms 856 KB Output is correct
30 Correct 479 ms 24064 KB Output is correct
31 Correct 250 ms 740 KB Output is correct
32 Correct 409 ms 20972 KB Output is correct
33 Correct 287 ms 732 KB Output is correct
34 Correct 276 ms 840 KB Output is correct
35 Correct 224 ms 852 KB Output is correct
36 Correct 364 ms 25112 KB Output is correct
37 Correct 325 ms 25112 KB Output is correct
38 Correct 548 ms 49596 KB Output is correct
39 Correct 502 ms 47032 KB Output is correct
40 Correct 268 ms 932 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 872 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 437 ms 884 KB Output is correct
4 Correct 459 ms 10112 KB Output is correct
5 Correct 15 ms 756 KB Output is correct
6 Correct 416 ms 2408 KB Output is correct
7 Correct 1 ms 400 KB Output is correct
8 Correct 255 ms 852 KB Output is correct
9 Correct 353 ms 1120 KB Output is correct
10 Correct 589 ms 27904 KB Output is correct
11 Correct 478 ms 24496 KB Output is correct
12 Correct 60 ms 632 KB Output is correct
13 Correct 385 ms 24772 KB Output is correct
14 Correct 435 ms 832 KB Output is correct
15 Correct 0 ms 400 KB Output is correct
16 Correct 370 ms 856 KB Output is correct
17 Correct 334 ms 892 KB Output is correct
18 Correct 297 ms 856 KB Output is correct
19 Correct 391 ms 828 KB Output is correct
20 Correct 299 ms 828 KB Output is correct
21 Correct 347 ms 808 KB Output is correct
22 Correct 285 ms 780 KB Output is correct
23 Correct 360 ms 804 KB Output is correct
24 Correct 159 ms 728 KB Output is correct
25 Correct 165 ms 832 KB Output is correct
26 Correct 260 ms 13264 KB Output is correct
27 Correct 144 ms 716 KB Output is correct
28 Correct 199 ms 9916 KB Output is correct
29 Correct 175 ms 692 KB Output is correct
30 Correct 127 ms 752 KB Output is correct
31 Correct 181 ms 756 KB Output is correct
32 Correct 284 ms 19440 KB Output is correct
33 Correct 245 ms 19500 KB Output is correct
34 Correct 416 ms 38292 KB Output is correct
35 Correct 334 ms 35956 KB Output is correct
36 Correct 155 ms 728 KB Output is correct
37 Correct 0 ms 400 KB Output is correct
38 Correct 205 ms 708 KB Output is correct
39 Correct 143 ms 688 KB Output is correct
40 Correct 209 ms 776 KB Output is correct
41 Correct 310 ms 10008 KB Output is correct
42 Correct 235 ms 836 KB Output is correct
43 Correct 269 ms 10236 KB Output is correct
44 Correct 228 ms 872 KB Output is correct
45 Correct 231 ms 800 KB Output is correct
46 Correct 281 ms 22556 KB Output is correct
47 Correct 271 ms 22328 KB Output is correct
48 Correct 497 ms 44256 KB Output is correct
49 Correct 446 ms 40688 KB Output is correct
50 Correct 165 ms 1104 KB Output is correct
51 Correct 199 ms 756 KB Output is correct
52 Correct 217 ms 856 KB Output is correct
53 Correct 479 ms 24064 KB Output is correct
54 Correct 250 ms 740 KB Output is correct
55 Correct 409 ms 20972 KB Output is correct
56 Correct 287 ms 732 KB Output is correct
57 Correct 276 ms 840 KB Output is correct
58 Correct 224 ms 852 KB Output is correct
59 Correct 364 ms 25112 KB Output is correct
60 Correct 325 ms 25112 KB Output is correct
61 Correct 548 ms 49596 KB Output is correct
62 Correct 502 ms 47032 KB Output is correct
63 Correct 268 ms 932 KB Output is correct
64 Correct 375 ms 1028 KB Output is correct
65 Runtime error 320 ms 13320 KB Execution killed with signal 13
66 Halted 0 ms 0 KB -