oj.uz

답안 #831765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831765 2023-08-20T13:49:38 Z NoName14159 Two Transportations (JOI19_transportations) C++17
84 / 100
 576 ms 49308 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=(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++;
assert(t!=n);
				if(!leader){
					bits_next=1;
					return;
				}
			}
		}
	}
}
void InitA(int N,int A,vi U,vi V,vi C){
	std::srand(7749);
	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=(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 B,vi S,vi T,vi D){
	std::srand(7749);
	n=N;
	LOOP(i,B){
		e[S[i]].pub({T[i],D[i]});
		e[T[i]].pub({S[i],D[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

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 808 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 314 ms 828 KB Output is correct
4 Correct 389 ms 10160 KB Output is correct
5 Correct 20 ms 1012 KB Output is correct
6 Correct 315 ms 2428 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 656 KB Output is correct
2 Correct 293 ms 832 KB Output is correct
3 Correct 317 ms 904 KB Output is correct
4 Correct 528 ms 27612 KB Output is correct
5 Correct 435 ms 24416 KB Output is correct
6 Correct 72 ms 756 KB Output is correct
7 Correct 513 ms 24584 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 816 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 340 ms 792 KB Output is correct
4 Correct 370 ms 856 KB Output is correct
5 Correct 233 ms 1056 KB Output is correct
6 Correct 391 ms 944 KB Output is correct
7 Correct 409 ms 800 KB Output is correct
8 Correct 376 ms 808 KB Output is correct
9 Correct 362 ms 916 KB Output is correct
10 Correct 344 ms 832 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 712 KB Output is correct
2 Correct 119 ms 920 KB Output is correct
3 Correct 296 ms 13304 KB Output is correct
4 Correct 186 ms 768 KB Output is correct
5 Correct 250 ms 10040 KB Output is correct
6 Correct 152 ms 748 KB Output is correct
7 Correct 182 ms 804 KB Output is correct
8 Correct 111 ms 800 KB Output is correct
9 Correct 194 ms 19480 KB Output is correct
10 Correct 244 ms 19508 KB Output is correct
11 Correct 394 ms 38380 KB Output is correct
12 Correct 355 ms 35884 KB Output is correct
13 Correct 155 ms 840 KB Output is correct
14 Correct 0 ms 656 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 712 KB Output is correct
2 Correct 119 ms 920 KB Output is correct
3 Correct 296 ms 13304 KB Output is correct
4 Correct 186 ms 768 KB Output is correct
5 Correct 250 ms 10040 KB Output is correct
6 Correct 152 ms 748 KB Output is correct
7 Correct 182 ms 804 KB Output is correct
8 Correct 111 ms 800 KB Output is correct
9 Correct 194 ms 19480 KB Output is correct
10 Correct 244 ms 19508 KB Output is correct
11 Correct 394 ms 38380 KB Output is correct
12 Correct 355 ms 35884 KB Output is correct
13 Correct 155 ms 840 KB Output is correct
14 Correct 0 ms 656 KB Output is correct
15 Correct 149 ms 704 KB Output is correct
16 Correct 233 ms 732 KB Output is correct
17 Correct 129 ms 728 KB Output is correct
18 Correct 279 ms 10112 KB Output is correct
19 Correct 207 ms 912 KB Output is correct
20 Correct 261 ms 10312 KB Output is correct
21 Correct 119 ms 824 KB Output is correct
22 Correct 186 ms 832 KB Output is correct
23 Correct 385 ms 22596 KB Output is correct
24 Correct 296 ms 22432 KB Output is correct
25 Correct 428 ms 44148 KB Output is correct
26 Correct 453 ms 40528 KB Output is correct
27 Correct 231 ms 888 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 712 KB Output is correct
2 Correct 119 ms 920 KB Output is correct
3 Correct 296 ms 13304 KB Output is correct
4 Correct 186 ms 768 KB Output is correct
5 Correct 250 ms 10040 KB Output is correct
6 Correct 152 ms 748 KB Output is correct
7 Correct 182 ms 804 KB Output is correct
8 Correct 111 ms 800 KB Output is correct
9 Correct 194 ms 19480 KB Output is correct
10 Correct 244 ms 19508 KB Output is correct
11 Correct 394 ms 38380 KB Output is correct
12 Correct 355 ms 35884 KB Output is correct
13 Correct 155 ms 840 KB Output is correct
14 Correct 0 ms 656 KB Output is correct
15 Correct 149 ms 704 KB Output is correct
16 Correct 233 ms 732 KB Output is correct
17 Correct 129 ms 728 KB Output is correct
18 Correct 279 ms 10112 KB Output is correct
19 Correct 207 ms 912 KB Output is correct
20 Correct 261 ms 10312 KB Output is correct
21 Correct 119 ms 824 KB Output is correct
22 Correct 186 ms 832 KB Output is correct
23 Correct 385 ms 22596 KB Output is correct
24 Correct 296 ms 22432 KB Output is correct
25 Correct 428 ms 44148 KB Output is correct
26 Correct 453 ms 40528 KB Output is correct
27 Correct 231 ms 888 KB Output is correct
28 Correct 251 ms 1004 KB Output is correct
29 Correct 209 ms 740 KB Output is correct
30 Correct 468 ms 24180 KB Output is correct
31 Correct 205 ms 756 KB Output is correct
32 Correct 436 ms 21064 KB Output is correct
33 Correct 252 ms 944 KB Output is correct
34 Correct 263 ms 1000 KB Output is correct
35 Correct 216 ms 872 KB Output is correct
36 Correct 435 ms 25024 KB Output is correct
37 Correct 398 ms 25020 KB Output is correct
38 Correct 576 ms 49308 KB Output is correct
39 Correct 419 ms 47376 KB Output is correct
40 Correct 328 ms 1196 KB Output is correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 808 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 314 ms 828 KB Output is correct
4 Correct 389 ms 10160 KB Output is correct
5 Correct 20 ms 1012 KB Output is correct
6 Correct 315 ms 2428 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 293 ms 832 KB Output is correct
9 Correct 317 ms 904 KB Output is correct
10 Correct 528 ms 27612 KB Output is correct
11 Correct 435 ms 24416 KB Output is correct
12 Correct 72 ms 756 KB Output is correct
13 Correct 513 ms 24584 KB Output is correct
14 Correct 354 ms 816 KB Output is correct
15 Correct 0 ms 656 KB Output is correct
16 Correct 340 ms 792 KB Output is correct
17 Correct 370 ms 856 KB Output is correct
18 Correct 233 ms 1056 KB Output is correct
19 Correct 391 ms 944 KB Output is correct
20 Correct 409 ms 800 KB Output is correct
21 Correct 376 ms 808 KB Output is correct
22 Correct 362 ms 916 KB Output is correct
23 Correct 344 ms 832 KB Output is correct
24 Correct 174 ms 712 KB Output is correct
25 Correct 119 ms 920 KB Output is correct
26 Correct 296 ms 13304 KB Output is correct
27 Correct 186 ms 768 KB Output is correct
28 Correct 250 ms 10040 KB Output is correct
29 Correct 152 ms 748 KB Output is correct
30 Correct 182 ms 804 KB Output is correct
31 Correct 111 ms 800 KB Output is correct
32 Correct 194 ms 19480 KB Output is correct
33 Correct 244 ms 19508 KB Output is correct
34 Correct 394 ms 38380 KB Output is correct
35 Correct 355 ms 35884 KB Output is correct
36 Correct 155 ms 840 KB Output is correct
37 Correct 0 ms 656 KB Output is correct
38 Correct 149 ms 704 KB Output is correct
39 Correct 233 ms 732 KB Output is correct
40 Correct 129 ms 728 KB Output is correct
41 Correct 279 ms 10112 KB Output is correct
42 Correct 207 ms 912 KB Output is correct
43 Correct 261 ms 10312 KB Output is correct
44 Correct 119 ms 824 KB Output is correct
45 Correct 186 ms 832 KB Output is correct
46 Correct 385 ms 22596 KB Output is correct
47 Correct 296 ms 22432 KB Output is correct
48 Correct 428 ms 44148 KB Output is correct
49 Correct 453 ms 40528 KB Output is correct
50 Correct 231 ms 888 KB Output is correct
51 Correct 251 ms 1004 KB Output is correct
52 Correct 209 ms 740 KB Output is correct
53 Correct 468 ms 24180 KB Output is correct
54 Correct 205 ms 756 KB Output is correct
55 Correct 436 ms 21064 KB Output is correct
56 Correct 252 ms 944 KB Output is correct
57 Correct 263 ms 1000 KB Output is correct
58 Correct 216 ms 872 KB Output is correct
59 Correct 435 ms 25024 KB Output is correct
60 Correct 398 ms 25020 KB Output is correct
61 Correct 576 ms 49308 KB Output is correct
62 Correct 419 ms 47376 KB Output is correct
63 Correct 328 ms 1196 KB Output is correct
64 Correct 319 ms 1156 KB Output is correct
65 Runtime error 292 ms 13256 KB Execution killed with signal 13
66 Halted 0 ms 0 KB -