oj.uz

답안 #134862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134862 2019-07-23T10:35:41 Z scanhex Two Transportations (JOI19_transportations) C++17
70 / 100
 1544 ms 85432 KB 
#include<bits/stdc++.h>
using namespace std;
#include "Azer.h"

namespace {
const int N=2020;
const int SZ=9;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	if(len==SZ)x=min(x,(1<<SZ)-1);
	for(int i=len-1;i>=0;--i)
		SendA(x>>i&1);
}
int receive(int len){
	assert(q.size()>=len);
	int ans=0;
	for(int i=0;i<len;++i)
		ans*=2,ans+=q.front(),q.pop_front();
	return ans;
}
int d[N];
int n;
const int oo=(1<<SZ)-1;
int state=0;
int rest=0;
int kek,mem;
auto cmp=[&](const int a,const int b){
	if(d[a]!=d[b])
		return d[a]<d[b];
	return a<b;
};
set<int,decltype(cmp)>st(cmp);
int last=0;
void relax(){
//	cerr<<"a "<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=mem;
	last=mem;
	for(auto& [a,b]:g[kek]){
		if(d[kek]+b<d[a]){
			st.erase(a);
			d[a]=d[kek]+b;
			st.insert(a);
		}
	}
}
void proc(){
	int num=0;
	for(int x:q)num*=2,num+=x;
	q.clear();
	if(!st.size())return;
	if(state==0){
		kek=*st.begin();
		mem=d[kek];
//		cerr<<"a "<<mem<<'\n';
		send(mem-last,SZ);
		state=1;
		rest=1;
		return;
	}
	if(state==1){
		if(num==1){
			send(kek,11);
			relax();
			state=0;
			proc();
			return;
		}
		else{
			state=2;
			rest=SZ;
			return;
		}
	}
	if(state==2){
		mem=num+last;
		state=3;
		rest=11;
		return;
	}
	if(state==3){
		kek=num;
		relax();
		state=0;
		proc();
		return;
	}
}
}  // namespace

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){
		g[U[i]].emplace_back(V[i],C[i]);
		g[V[i]].emplace_back(U[i],C[i]);
	}
	fill(d,d+n,1<<20);
	d[0]=0;
	for(int i=0;i<n;++i)st.insert(i);
	proc();
}

void ReceiveA(bool x) {
	q.push_back(x);
	if(--rest==0){
		proc();
	}
}

std::vector<int> Answer() {
	vector<int>ans(d,d+n);
	return ans;
}

#include<bits/stdc++.h>
using namespace std;
#include "Baijan.h"

namespace {
const int N=2020;
const int SZ=9;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	if(len==SZ)x=min(x,(1<<SZ)-1);
	for(int i=len-1;i>=0;--i)
		SendB(x>>i&1);
}
int receive(int len){
	assert(q.size()>=len);
	int ans=0;
	for(int i=0;i<len;++i)
		ans*=2,ans+=q.front(),q.pop_front();
	return ans;
}
int d[N];
int n;
const int oo=(1<<SZ)-1;
int rest=0;
int state=0;
int kek,mem;
auto cmp=[&](const int a,const int b){
	if(d[a]!=d[b])
		return d[a]<d[b];
	return a<b;
};
set<int,decltype(cmp)>st(cmp);
int last=0;
void relax(){
//	cerr<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=mem;
	last=mem;
	for(auto& [a,b]:g[kek]){
		if(d[kek]+b<d[a]){
			st.erase(a);
			d[a]=d[kek]+b;
			st.insert(a);
		}
	}
}

void proc(){
	int num=0;
	for(int x:q)num*=2,num+=x;
	q.clear();
//	cerr<<num<<'\n';
	if(!st.size())return;
	if(state==0){
		kek=*st.begin();
		mem=d[kek];
		int di=num+last;
//		cerr<<di<<'\n';
		if(mem>=di){
			send(1,1);
			mem=di;
			state=1;
			rest=11;
			return;
		}
		else{
//			cerr<<"rofl\n";
			send(0,1);
			send(mem-last,SZ);
			send(kek,11);
			state=0;
			rest=SZ;
			relax();
			return;
		}
	}
	if(state==1){
		kek=num;
		relax();
		state=0;
		rest=SZ;
		return;
	}
}
}  // namespace

void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
	n=N;
	for(int i=0;i<B;++i){
		g[U[i]].emplace_back(V[i],C[i]);
		g[V[i]].emplace_back(U[i],C[i]);
	}
	fill(d,d+n,1<<20);
	d[0]=0;
	for(int i=0;i<n;++i)st.insert(i);
	rest=SZ;
}


void ReceiveB(bool y) {
	q.push_back(y);
	if(--rest==0)proc();
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Azer.cpp:1:
Azer.cpp: In function 'int {anonymous}::receive(int)':
Azer.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Azer.cpp: At global scope:
Azer.cpp:15:5: warning: 'int {anonymous}::receive(int)' defined but not used [-Wunused-function]
 int receive(int len){
     ^~~~~~~

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Baijan.cpp:1:
Baijan.cpp: In function 'int {anonymous}::receive(int)':
Baijan.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Baijan.cpp: At global scope:
Baijan.cpp:15:5: warning: 'int {anonymous}::receive(int)' defined but not used [-Wunused-function]
 int receive(int len){
     ^~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 630 ms 872 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1208 KB Output is correct
2 Correct 898 ms 2208 KB Output is correct
3 Correct 1004 ms 2048 KB Output is correct
4 Correct 910 ms 55168 KB Output is correct
5 Correct 1267 ms 48312 KB Output is correct
6 Correct 216 ms 1504 KB Output is correct
7 Correct 1480 ms 48552 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1109 ms 2016 KB Output is correct
2 Correct 4 ms 960 KB Output is correct
3 Incorrect 544 ms 884 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 1544 KB Output is correct
2 Correct 382 ms 1760 KB Output is correct
3 Correct 578 ms 23720 KB Output is correct
4 Correct 430 ms 1768 KB Output is correct
5 Correct 632 ms 17376 KB Output is correct
6 Correct 469 ms 1448 KB Output is correct
7 Correct 434 ms 1592 KB Output is correct
8 Correct 380 ms 1640 KB Output is correct
9 Correct 715 ms 36096 KB Output is correct
10 Correct 802 ms 36080 KB Output is correct
11 Correct 1108 ms 61040 KB Output is correct
12 Correct 906 ms 53584 KB Output is correct
13 Correct 382 ms 2080 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 1544 KB Output is correct
2 Correct 382 ms 1760 KB Output is correct
3 Correct 578 ms 23720 KB Output is correct
4 Correct 430 ms 1768 KB Output is correct
5 Correct 632 ms 17376 KB Output is correct
6 Correct 469 ms 1448 KB Output is correct
7 Correct 434 ms 1592 KB Output is correct
8 Correct 380 ms 1640 KB Output is correct
9 Correct 715 ms 36096 KB Output is correct
10 Correct 802 ms 36080 KB Output is correct
11 Correct 1108 ms 61040 KB Output is correct
12 Correct 906 ms 53584 KB Output is correct
13 Correct 382 ms 2080 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct
15 Correct 530 ms 1536 KB Output is correct
16 Correct 438 ms 1712 KB Output is correct
17 Correct 456 ms 1584 KB Output is correct
18 Correct 716 ms 17664 KB Output is correct
19 Correct 576 ms 1600 KB Output is correct
20 Correct 670 ms 18032 KB Output is correct
21 Correct 458 ms 1760 KB Output is correct
22 Correct 394 ms 1776 KB Output is correct
23 Correct 831 ms 44160 KB Output is correct
24 Correct 940 ms 44024 KB Output is correct
25 Correct 1172 ms 74880 KB Output is correct
26 Correct 1180 ms 63840 KB Output is correct
27 Correct 447 ms 1856 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 1544 KB Output is correct
2 Correct 382 ms 1760 KB Output is correct
3 Correct 578 ms 23720 KB Output is correct
4 Correct 430 ms 1768 KB Output is correct
5 Correct 632 ms 17376 KB Output is correct
6 Correct 469 ms 1448 KB Output is correct
7 Correct 434 ms 1592 KB Output is correct
8 Correct 380 ms 1640 KB Output is correct
9 Correct 715 ms 36096 KB Output is correct
10 Correct 802 ms 36080 KB Output is correct
11 Correct 1108 ms 61040 KB Output is correct
12 Correct 906 ms 53584 KB Output is correct
13 Correct 382 ms 2080 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct
15 Correct 530 ms 1536 KB Output is correct
16 Correct 438 ms 1712 KB Output is correct
17 Correct 456 ms 1584 KB Output is correct
18 Correct 716 ms 17664 KB Output is correct
19 Correct 576 ms 1600 KB Output is correct
20 Correct 670 ms 18032 KB Output is correct
21 Correct 458 ms 1760 KB Output is correct
22 Correct 394 ms 1776 KB Output is correct
23 Correct 831 ms 44160 KB Output is correct
24 Correct 940 ms 44024 KB Output is correct
25 Correct 1172 ms 74880 KB Output is correct
26 Correct 1180 ms 63840 KB Output is correct
27 Correct 447 ms 1856 KB Output is correct
28 Correct 602 ms 1760 KB Output is correct
29 Correct 774 ms 1672 KB Output is correct
30 Correct 894 ms 42144 KB Output is correct
31 Correct 812 ms 1688 KB Output is correct
32 Correct 988 ms 37568 KB Output is correct
33 Correct 682 ms 1728 KB Output is correct
34 Correct 781 ms 2080 KB Output is correct
35 Correct 826 ms 2136 KB Output is correct
36 Correct 960 ms 49192 KB Output is correct
37 Correct 1252 ms 49240 KB Output is correct
38 Correct 1544 ms 85432 KB Output is correct
39 Correct 1448 ms 78344 KB Output is correct
40 Correct 728 ms 2128 KB Output is correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 630 ms 872 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -