oj.uz

Submission #784268

# Submission time Handle Problem Language Result Execution time Memory
784268 2023-07-15T23:18:40 Z AdamGS Two Transportations (JOI19_transportations) C++17
100 / 100
 986 ms 57688 KB 
#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
	const int LIM=2e3+7, INF=1e9+7;
	vector<pair<int,int>>V[LIM];
	int odl[LIM];
	int n, lst=0;
	int akt=0, li=0, stan=0;
	int moje, jego;
	priority_queue<pair<int,int>>q;
void wyslij(int x) {
	rep(i, 9) if(x&(1<<i)) SendA(1); else SendA(0);
}
void wyslij2(int x) {
	rep(i, 11) if(x&(1<<i)) SendA(1); else SendA(0);
}
void wysylam_odl() {
	while(!q.empty() && odl[q.top().nd]<INF) q.pop();
	if(!q.empty()) {
		moje=-q.top().st-lst;
		wyslij(moje);
	} else {
		moje=511;
		wyslij(moje);
	}
}
void wrzuc(int dys, int wierz) {
	dys+=lst;
	lst=dys;
	odl[wierz]=dys;
	for(auto i : V[wierz]) q.push({-odl[wierz]-i.nd, i.st});
}
}
void InitA(int _N, int _A, vector<int>A, vector<int>B, vector<int>C) {
	n=_N;
	rep(i, _A) {
		V[A[i]].pb({B[i], C[i]});
		V[B[i]].pb({A[i], C[i]});
	}
	rep(i, n) odl[i]=INF; 
	wrzuc(0, 0);
	wysylam_odl();
}
void ReceiveA(bool x) {
	if(x) li+=1<<akt;
	++akt;
	if(stan==0 && akt==9) {
		if(li==511) return;
		if(li<moje) {
			jego=li;
			akt=li=0;
			stan=1;
		} else {
			int dys=-q.top().st, wierz=q.top().nd; q.pop();
			wyslij2(wierz);
			wrzuc(dys-lst, wierz);
			akt=li=0;
			stan=2;
		}
	} else if(stan==1 && akt==11) {
		wrzuc(jego, li);
		akt=li=0;
		wysylam_odl();
		stan=0;
	} else if(stan==2 && akt==9) {
		jego=li;
		while(!q.empty() && odl[q.top().nd]<INF) q.pop();
		if(q.empty()) {
			wyslij(li);
			stan=1;
			akt=li=0;
			return;
		}
		int dys=-q.top().st, wierz=q.top().nd;
		if(dys-lst<li) {
			wyslij(dys-lst);
			wyslij2(wierz);
			q.pop();
			wrzuc(dys-lst, wierz);
			stan=2;
		} else {
			wyslij(li);
			stan=1;
		}
		akt=li=0;
	}
}
vector<int> Answer() {
  vector<int> ans(n);
  rep(i, n) ans[i]=odl[i];
  return ans;
}

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
	const int LIM=2e3+7, INF=1e9+7;
	vector<pair<int,int>>V[LIM];
	int odl[LIM];
	int n, lst=0;
	int akt=0, li=0, stan=0;
	int moje, jego;
	priority_queue<pair<int,int>>q;
void wyslij(int x) {
	rep(i, 9) if(x&(1<<i)) SendB(1); else SendB(0);
}
void wyslij2(int x) {
	rep(i, 11) if(x&(1<<i)) SendB(1); else SendB(0);
}
void wysylam_odl() {
	while(!q.empty() && odl[q.top().nd]<INF) q.pop();
	if(!q.empty()) {
		moje=-q.top().st-lst;
		wyslij(moje);
	} else {
		moje=511;
		wyslij(moje);
	}
}
void wrzuc(int dys, int wierz) {
	dys+=lst;
	lst=dys;
	odl[wierz]=dys;
	for(auto i : V[wierz]) q.push({-odl[wierz]-i.nd, i.st});
}
}
void InitB(int _N, int _A, vector<int>A, vector<int>B, vector<int>C) {
	n=_N;
	rep(i, _A) {
		V[A[i]].pb({B[i], C[i]});
		V[B[i]].pb({A[i], C[i]});
	}
	rep(i, n) odl[i]=INF;
	wrzuc(0, 0);
	stan=2;
}
void ReceiveB(bool x) {
	if(x) li+=1<<akt;
	++akt;
	if(stan==0 && akt==9) {
		if(li==511) return;
		if(li<moje) {
			jego=li;
			akt=li=0;
			stan=1;
		} else {
			int dys=-q.top().st, wierz=q.top().nd; q.pop();
			wyslij2(wierz);
			wrzuc(dys-lst, wierz);
			akt=li=0;
			stan=2;
		}
	} else if(stan==1 && akt==11) {
		wrzuc(jego, li);
		akt=li=0;
		wysylam_odl();
		stan=0;
	} else if(stan==2 && akt==9) {
		jego=li;
		while(!q.empty() && odl[q.top().nd]<INF) q.pop();
		if(q.empty()) {
			wyslij(li);
			stan=1;
			akt=li=0;
			return;
		}
		int dys=-q.top().st, wierz=q.top().nd;
		if(dys-lst<li) {
			wyslij(dys-lst);
			wyslij2(wierz);
			q.pop();
			wrzuc(dys-lst, wierz);
			stan=2;
		} else {
			wyslij(li);
			stan=1;
		}
		akt=li=0;
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 784 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 410 ms 788 KB Output is correct
4 Correct 463 ms 10136 KB Output is correct
5 Correct 28 ms 1068 KB Output is correct
6 Correct 373 ms 2724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 656 KB Output is correct
2 Correct 371 ms 740 KB Output is correct
3 Correct 345 ms 808 KB Output is correct
4 Correct 697 ms 27524 KB Output is correct
5 Correct 709 ms 28428 KB Output is correct
6 Correct 78 ms 656 KB Output is correct
7 Correct 688 ms 28616 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 728 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 458 ms 656 KB Output is correct
4 Correct 439 ms 744 KB Output is correct
5 Correct 301 ms 744 KB Output is correct
6 Correct 429 ms 732 KB Output is correct
7 Correct 395 ms 748 KB Output is correct
8 Correct 330 ms 668 KB Output is correct
9 Correct 405 ms 656 KB Output is correct
10 Correct 373 ms 944 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 688 KB Output is correct
2 Correct 182 ms 660 KB Output is correct
3 Correct 296 ms 13184 KB Output is correct
4 Correct 172 ms 708 KB Output is correct
5 Correct 292 ms 10108 KB Output is correct
6 Correct 193 ms 700 KB Output is correct
7 Correct 208 ms 656 KB Output is correct
8 Correct 215 ms 656 KB Output is correct
9 Correct 396 ms 23804 KB Output is correct
10 Correct 429 ms 23736 KB Output is correct
11 Correct 616 ms 47036 KB Output is correct
12 Correct 488 ms 44344 KB Output is correct
13 Correct 185 ms 852 KB Output is correct
14 Correct 2 ms 656 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 688 KB Output is correct
2 Correct 182 ms 660 KB Output is correct
3 Correct 296 ms 13184 KB Output is correct
4 Correct 172 ms 708 KB Output is correct
5 Correct 292 ms 10108 KB Output is correct
6 Correct 193 ms 700 KB Output is correct
7 Correct 208 ms 656 KB Output is correct
8 Correct 215 ms 656 KB Output is correct
9 Correct 396 ms 23804 KB Output is correct
10 Correct 429 ms 23736 KB Output is correct
11 Correct 616 ms 47036 KB Output is correct
12 Correct 488 ms 44344 KB Output is correct
13 Correct 185 ms 852 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Correct 228 ms 696 KB Output is correct
16 Correct 178 ms 720 KB Output is correct
17 Correct 244 ms 716 KB Output is correct
18 Correct 371 ms 10116 KB Output is correct
19 Correct 259 ms 720 KB Output is correct
20 Correct 357 ms 10320 KB Output is correct
21 Correct 165 ms 744 KB Output is correct
22 Correct 222 ms 656 KB Output is correct
23 Correct 503 ms 26732 KB Output is correct
24 Correct 509 ms 26508 KB Output is correct
25 Correct 760 ms 52368 KB Output is correct
26 Correct 665 ms 48816 KB Output is correct
27 Correct 253 ms 888 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 688 KB Output is correct
2 Correct 182 ms 660 KB Output is correct
3 Correct 296 ms 13184 KB Output is correct
4 Correct 172 ms 708 KB Output is correct
5 Correct 292 ms 10108 KB Output is correct
6 Correct 193 ms 700 KB Output is correct
7 Correct 208 ms 656 KB Output is correct
8 Correct 215 ms 656 KB Output is correct
9 Correct 396 ms 23804 KB Output is correct
10 Correct 429 ms 23736 KB Output is correct
11 Correct 616 ms 47036 KB Output is correct
12 Correct 488 ms 44344 KB Output is correct
13 Correct 185 ms 852 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Correct 228 ms 696 KB Output is correct
16 Correct 178 ms 720 KB Output is correct
17 Correct 244 ms 716 KB Output is correct
18 Correct 371 ms 10116 KB Output is correct
19 Correct 259 ms 720 KB Output is correct
20 Correct 357 ms 10320 KB Output is correct
21 Correct 165 ms 744 KB Output is correct
22 Correct 222 ms 656 KB Output is correct
23 Correct 503 ms 26732 KB Output is correct
24 Correct 509 ms 26508 KB Output is correct
25 Correct 760 ms 52368 KB Output is correct
26 Correct 665 ms 48816 KB Output is correct
27 Correct 253 ms 888 KB Output is correct
28 Correct 300 ms 708 KB Output is correct
29 Correct 273 ms 660 KB Output is correct
30 Correct 558 ms 24080 KB Output is correct
31 Correct 213 ms 656 KB Output is correct
32 Correct 465 ms 21056 KB Output is correct
33 Correct 287 ms 732 KB Output is correct
34 Correct 278 ms 760 KB Output is correct
35 Correct 339 ms 768 KB Output is correct
36 Correct 530 ms 29096 KB Output is correct
37 Correct 523 ms 29172 KB Output is correct
38 Correct 817 ms 57688 KB Output is correct
39 Correct 736 ms 55628 KB Output is correct
40 Correct 319 ms 1076 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 784 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 410 ms 788 KB Output is correct
4 Correct 463 ms 10136 KB Output is correct
5 Correct 28 ms 1068 KB Output is correct
6 Correct 373 ms 2724 KB Output is correct
7 Correct 1 ms 656 KB Output is correct
8 Correct 371 ms 740 KB Output is correct
9 Correct 345 ms 808 KB Output is correct
10 Correct 697 ms 27524 KB Output is correct
11 Correct 709 ms 28428 KB Output is correct
12 Correct 78 ms 656 KB Output is correct
13 Correct 688 ms 28616 KB Output is correct
14 Correct 446 ms 728 KB Output is correct
15 Correct 1 ms 656 KB Output is correct
16 Correct 458 ms 656 KB Output is correct
17 Correct 439 ms 744 KB Output is correct
18 Correct 301 ms 744 KB Output is correct
19 Correct 429 ms 732 KB Output is correct
20 Correct 395 ms 748 KB Output is correct
21 Correct 330 ms 668 KB Output is correct
22 Correct 405 ms 656 KB Output is correct
23 Correct 373 ms 944 KB Output is correct
24 Correct 220 ms 688 KB Output is correct
25 Correct 182 ms 660 KB Output is correct
26 Correct 296 ms 13184 KB Output is correct
27 Correct 172 ms 708 KB Output is correct
28 Correct 292 ms 10108 KB Output is correct
29 Correct 193 ms 700 KB Output is correct
30 Correct 208 ms 656 KB Output is correct
31 Correct 215 ms 656 KB Output is correct
32 Correct 396 ms 23804 KB Output is correct
33 Correct 429 ms 23736 KB Output is correct
34 Correct 616 ms 47036 KB Output is correct
35 Correct 488 ms 44344 KB Output is correct
36 Correct 185 ms 852 KB Output is correct
37 Correct 2 ms 656 KB Output is correct
38 Correct 228 ms 696 KB Output is correct
39 Correct 178 ms 720 KB Output is correct
40 Correct 244 ms 716 KB Output is correct
41 Correct 371 ms 10116 KB Output is correct
42 Correct 259 ms 720 KB Output is correct
43 Correct 357 ms 10320 KB Output is correct
44 Correct 165 ms 744 KB Output is correct
45 Correct 222 ms 656 KB Output is correct
46 Correct 503 ms 26732 KB Output is correct
47 Correct 509 ms 26508 KB Output is correct
48 Correct 760 ms 52368 KB Output is correct
49 Correct 665 ms 48816 KB Output is correct
50 Correct 253 ms 888 KB Output is correct
51 Correct 300 ms 708 KB Output is correct
52 Correct 273 ms 660 KB Output is correct
53 Correct 558 ms 24080 KB Output is correct
54 Correct 213 ms 656 KB Output is correct
55 Correct 465 ms 21056 KB Output is correct
56 Correct 287 ms 732 KB Output is correct
57 Correct 278 ms 760 KB Output is correct
58 Correct 339 ms 768 KB Output is correct
59 Correct 530 ms 29096 KB Output is correct
60 Correct 523 ms 29172 KB Output is correct
61 Correct 817 ms 57688 KB Output is correct
62 Correct 736 ms 55628 KB Output is correct
63 Correct 319 ms 1076 KB Output is correct
64 Correct 424 ms 952 KB Output is correct
65 Correct 724 ms 26616 KB Output is correct
66 Correct 659 ms 23344 KB Output is correct
67 Correct 415 ms 932 KB Output is correct
68 Correct 413 ms 936 KB Output is correct
69 Correct 986 ms 56424 KB Output is correct
70 Correct 933 ms 49464 KB Output is correct
71 Correct 461 ms 6452 KB Output is correct
72 Correct 414 ms 1392 KB Output is correct