답안 #720588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720588	2023-04-08T14:57:21 Z	qwerasdfzxcl	Two Transportations (JOI19_transportations)	C++17	100 / 100	831 ms	48972 KB

Azer
Baijan

#include "Azer.h"
#include <bits/stdc++.h>
constexpr int INF = 1e9 + 100;

using namespace std;
typedef long long ll;

namespace {

vector<pair<int, int>> adj[2020];
int n, dist[2020], visited[2020];
int mx, valA, valB, idxA, idxB, typ;

vector<int> buf;

}  // namespace


void updateA(int x, int v){
	visited[x] = 1;
	dist[x] = mx + v;
	mx += v;

	for (auto &[nx, w]:adj[x]) dist[nx] = min(dist[nx], dist[x] + w);
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
	n = N;
	for (int i=0;i<A;i++){
		adj[U[i]+1].emplace_back(V[i]+1, C[i]);
		adj[V[i]+1].emplace_back(U[i]+1, C[i]);
	}

	mx = 0, typ = 1;
	fill(dist+2, dist+n+1, INF);
	updateA(1, 0);
}

void cmpA(){
	valA = INF, valB = 0;
	idxA = -1;

	for (int i=1;i<=n;i++) if (!visited[i] && valA > dist[i]) valA = dist[i], idxA = i;
	valA = min(valA-mx, 511);
	for (int i=0;i<9;i++) if (buf[i]) valB |= 1<<i;
	buf.clear();

	for (int i=0;i<9;i++) SendA(valA&(1<<i));

	if (valA <= valB){
		for (int i=0;i<11;i++) SendA(idxA&(1<<i));
		updateA(idxA, valA);
	}
	else{
		typ = 2;
	}
}

void getA(){
	idxB = 0;
	for (int i=0;i<11;i++) if (buf[i]) idxB |= 1<<i;
	buf.clear();

	updateA(idxB, valB);
	typ = 1;
}

void ReceiveA(bool x) {
	buf.push_back(x);
	if (typ==1 && buf.size()==9) cmpA();
	if (typ==2 && buf.size()==11) getA();
}

std::vector<int> Answer() {
	vector<int> ans;
	for (int i=1;i<=n;i++) ans.push_back(dist[i]);
	return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
constexpr int INF = 1e9 + 100;

using namespace std;
typedef long long ll;

namespace {

vector<pair<int, int>> adj[2020];
int n, dist[2020], visited[2020];
int mx, valA, valB, idxA, idxB, typ;
int cntB;

vector<int> buf;

}  // namespace

void updateB(int x, int v){
	++cntB;
	visited[x] = 1;
	dist[x] = mx + v;
	mx += v;

	for (auto &[nx, w]:adj[x]) dist[nx] = min(dist[nx], dist[x] + w);

	valB = INF, idxB = -1;
	for (int i=1;i<=n;i++) if (!visited[i] && valB > dist[i]) valB = dist[i], idxB = i;
	valB = min(valB-mx, 511);
	if (cntB==n) return;

	for (int i=0;i<9;i++) SendB(valB&(1<<i));
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
	n = N;
	for (int i=0;i<B;i++){
		adj[S[i]+1].emplace_back(T[i]+1, D[i]);
		adj[T[i]+1].emplace_back(S[i]+1, D[i]);
	}

	mx = 0, typ = 1;
	fill(dist+2, dist+n+1, INF);
	updateB(1, 0);
}

void checkB(){
	valA = 0;
	for (int i=0;i<9;i++) if (buf[i]) valA |= 1<<i;
	buf.clear();

	if (valA <= valB){
		typ = 2;
	}
	else{
		for (int i=0;i<11;i++) SendB(idxB&(1<<i));
		updateB(idxB, valB);
	}
}

void getB(){
	idxA = 0;
	for (int i=0;i<11;i++) if (buf[i]) idxA |= 1<<i;
	buf.clear();

	updateB(idxA, valA);
	typ = 1;
}

void ReceiveB(bool y) {
	buf.push_back(y);
	if (typ==1 && buf.size()==9) checkB();
	if (typ==2 && buf.size()==11) getB();
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	578 ms	796 KB	Output is correct
2	Correct	2 ms	800 KB	Output is correct
3	Correct	463 ms	796 KB	Output is correct
4	Correct	588 ms	10160 KB	Output is correct
5	Correct	27 ms	912 KB	Output is correct
6	Correct	610 ms	2188 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	656 KB	Output is correct
2	Correct	544 ms	760 KB	Output is correct
3	Correct	502 ms	904 KB	Output is correct
4	Correct	595 ms	27536 KB	Output is correct
5	Correct	670 ms	24084 KB	Output is correct
6	Correct	106 ms	660 KB	Output is correct
7	Correct	671 ms	24400 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	564 ms	864 KB	Output is correct
2	Correct	0 ms	656 KB	Output is correct
3	Correct	424 ms	752 KB	Output is correct
4	Correct	523 ms	756 KB	Output is correct
5	Correct	618 ms	756 KB	Output is correct
6	Correct	608 ms	744 KB	Output is correct
7	Correct	470 ms	764 KB	Output is correct
8	Correct	497 ms	808 KB	Output is correct
9	Correct	414 ms	796 KB	Output is correct
10	Correct	536 ms	812 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	700 KB	Output is correct
2	Correct	259 ms	668 KB	Output is correct
3	Correct	312 ms	13300 KB	Output is correct
4	Correct	273 ms	656 KB	Output is correct
5	Correct	316 ms	10116 KB	Output is correct
6	Correct	190 ms	704 KB	Output is correct
7	Correct	236 ms	656 KB	Output is correct
8	Correct	212 ms	744 KB	Output is correct
9	Correct	330 ms	18088 KB	Output is correct
10	Correct	326 ms	18228 KB	Output is correct
11	Correct	465 ms	35748 KB	Output is correct
12	Correct	360 ms	30624 KB	Output is correct
13	Correct	240 ms	656 KB	Output is correct
14	Correct	1 ms	656 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	700 KB	Output is correct
2	Correct	259 ms	668 KB	Output is correct
3	Correct	312 ms	13300 KB	Output is correct
4	Correct	273 ms	656 KB	Output is correct
5	Correct	316 ms	10116 KB	Output is correct
6	Correct	190 ms	704 KB	Output is correct
7	Correct	236 ms	656 KB	Output is correct
8	Correct	212 ms	744 KB	Output is correct
9	Correct	330 ms	18088 KB	Output is correct
10	Correct	326 ms	18228 KB	Output is correct
11	Correct	465 ms	35748 KB	Output is correct
12	Correct	360 ms	30624 KB	Output is correct
13	Correct	240 ms	656 KB	Output is correct
14	Correct	1 ms	656 KB	Output is correct
15	Correct	280 ms	700 KB	Output is correct
16	Correct	263 ms	748 KB	Output is correct
17	Correct	255 ms	752 KB	Output is correct
18	Correct	295 ms	10124 KB	Output is correct
19	Correct	299 ms	728 KB	Output is correct
20	Correct	368 ms	10284 KB	Output is correct
21	Correct	224 ms	756 KB	Output is correct
22	Correct	302 ms	656 KB	Output is correct
23	Correct	411 ms	22152 KB	Output is correct
24	Correct	396 ms	22152 KB	Output is correct
25	Correct	538 ms	43628 KB	Output is correct
26	Correct	425 ms	36348 KB	Output is correct
27	Correct	262 ms	784 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	215 ms	700 KB	Output is correct
2	Correct	259 ms	668 KB	Output is correct
3	Correct	312 ms	13300 KB	Output is correct
4	Correct	273 ms	656 KB	Output is correct
5	Correct	316 ms	10116 KB	Output is correct
6	Correct	190 ms	704 KB	Output is correct
7	Correct	236 ms	656 KB	Output is correct
8	Correct	212 ms	744 KB	Output is correct
9	Correct	330 ms	18088 KB	Output is correct
10	Correct	326 ms	18228 KB	Output is correct
11	Correct	465 ms	35748 KB	Output is correct
12	Correct	360 ms	30624 KB	Output is correct
13	Correct	240 ms	656 KB	Output is correct
14	Correct	1 ms	656 KB	Output is correct
15	Correct	280 ms	700 KB	Output is correct
16	Correct	263 ms	748 KB	Output is correct
17	Correct	255 ms	752 KB	Output is correct
18	Correct	295 ms	10124 KB	Output is correct
19	Correct	299 ms	728 KB	Output is correct
20	Correct	368 ms	10284 KB	Output is correct
21	Correct	224 ms	756 KB	Output is correct
22	Correct	302 ms	656 KB	Output is correct
23	Correct	411 ms	22152 KB	Output is correct
24	Correct	396 ms	22152 KB	Output is correct
25	Correct	538 ms	43628 KB	Output is correct
26	Correct	425 ms	36348 KB	Output is correct
27	Correct	262 ms	784 KB	Output is correct
28	Correct	388 ms	716 KB	Output is correct
29	Correct	376 ms	768 KB	Output is correct
30	Correct	570 ms	23932 KB	Output is correct
31	Correct	343 ms	764 KB	Output is correct
32	Correct	479 ms	21044 KB	Output is correct
33	Correct	286 ms	740 KB	Output is correct
34	Correct	359 ms	1024 KB	Output is correct
35	Correct	380 ms	912 KB	Output is correct
36	Correct	444 ms	24708 KB	Output is correct
37	Correct	491 ms	24728 KB	Output is correct
38	Correct	603 ms	48972 KB	Output is correct
39	Correct	538 ms	44208 KB	Output is correct
40	Correct	289 ms	952 KB	Output is correct

Subtask #7
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	578 ms	796 KB	Output is correct
2	Correct	2 ms	800 KB	Output is correct
3	Correct	463 ms	796 KB	Output is correct
4	Correct	588 ms	10160 KB	Output is correct
5	Correct	27 ms	912 KB	Output is correct
6	Correct	610 ms	2188 KB	Output is correct
7	Correct	0 ms	656 KB	Output is correct
8	Correct	544 ms	760 KB	Output is correct
9	Correct	502 ms	904 KB	Output is correct
10	Correct	595 ms	27536 KB	Output is correct
11	Correct	670 ms	24084 KB	Output is correct
12	Correct	106 ms	660 KB	Output is correct
13	Correct	671 ms	24400 KB	Output is correct
14	Correct	564 ms	864 KB	Output is correct
15	Correct	0 ms	656 KB	Output is correct
16	Correct	424 ms	752 KB	Output is correct
17	Correct	523 ms	756 KB	Output is correct
18	Correct	618 ms	756 KB	Output is correct
19	Correct	608 ms	744 KB	Output is correct
20	Correct	470 ms	764 KB	Output is correct
21	Correct	497 ms	808 KB	Output is correct
22	Correct	414 ms	796 KB	Output is correct
23	Correct	536 ms	812 KB	Output is correct
24	Correct	215 ms	700 KB	Output is correct
25	Correct	259 ms	668 KB	Output is correct
26	Correct	312 ms	13300 KB	Output is correct
27	Correct	273 ms	656 KB	Output is correct
28	Correct	316 ms	10116 KB	Output is correct
29	Correct	190 ms	704 KB	Output is correct
30	Correct	236 ms	656 KB	Output is correct
31	Correct	212 ms	744 KB	Output is correct
32	Correct	330 ms	18088 KB	Output is correct
33	Correct	326 ms	18228 KB	Output is correct
34	Correct	465 ms	35748 KB	Output is correct
35	Correct	360 ms	30624 KB	Output is correct
36	Correct	240 ms	656 KB	Output is correct
37	Correct	1 ms	656 KB	Output is correct
38	Correct	280 ms	700 KB	Output is correct
39	Correct	263 ms	748 KB	Output is correct
40	Correct	255 ms	752 KB	Output is correct
41	Correct	295 ms	10124 KB	Output is correct
42	Correct	299 ms	728 KB	Output is correct
43	Correct	368 ms	10284 KB	Output is correct
44	Correct	224 ms	756 KB	Output is correct
45	Correct	302 ms	656 KB	Output is correct
46	Correct	411 ms	22152 KB	Output is correct
47	Correct	396 ms	22152 KB	Output is correct
48	Correct	538 ms	43628 KB	Output is correct
49	Correct	425 ms	36348 KB	Output is correct
50	Correct	262 ms	784 KB	Output is correct
51	Correct	388 ms	716 KB	Output is correct
52	Correct	376 ms	768 KB	Output is correct
53	Correct	570 ms	23932 KB	Output is correct
54	Correct	343 ms	764 KB	Output is correct
55	Correct	479 ms	21044 KB	Output is correct
56	Correct	286 ms	740 KB	Output is correct
57	Correct	359 ms	1024 KB	Output is correct
58	Correct	380 ms	912 KB	Output is correct
59	Correct	444 ms	24708 KB	Output is correct
60	Correct	491 ms	24728 KB	Output is correct
61	Correct	603 ms	48972 KB	Output is correct
62	Correct	538 ms	44208 KB	Output is correct
63	Correct	289 ms	952 KB	Output is correct
64	Correct	463 ms	964 KB	Output is correct
65	Correct	520 ms	26516 KB	Output is correct
66	Correct	645 ms	23360 KB	Output is correct
67	Correct	556 ms	968 KB	Output is correct
68	Correct	525 ms	948 KB	Output is correct
69	Correct	741 ms	47604 KB	Output is correct
70	Correct	831 ms	39544 KB	Output is correct
71	Correct	546 ms	5048 KB	Output is correct
72	Correct	510 ms	1168 KB	Output is correct

답안 #720588

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 8.0 / 8.0

Subtask #4 38.0 / 38.0

Subtask #5 14.0 / 14.0

Subtask #6 10.0 / 10.0

Subtask #7 16.0 / 16.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
8.0 / 8.0

Subtask #4
38.0 / 38.0

Subtask #5
14.0 / 14.0

Subtask #6
10.0 / 10.0

Subtask #7
16.0 / 16.0