oj.uz

Submission #134860

# Submission time Handle Problem Language Result Execution time Memory
134860 2019-07-23T10:29:58 Z scanhex Two Transportations (JOI19_transportations) C++17
52 / 100
 1540 ms 74928 KB 
#include<bits/stdc++.h>
using namespace std;
#include "Azer.h"

namespace {
const int N=2020;
const int SZ=20;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	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);
void relax(){
//	cerr<<"a "<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=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,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;
		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,oo);
	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=20;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	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);
void relax(){
//	cerr<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=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;
//		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,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,oo);
	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:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Azer.cpp: At global scope:
Azer.cpp:14: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:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Baijan.cpp: At global scope:
Baijan.cpp:14:5: warning: 'int {anonymous}::receive(int)' defined but not used [-Wunused-function]
 int receive(int len){
     ^~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 924 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1264 KB Output is correct
2 Incorrect 468 ms 1136 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 912 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 1760 KB Output is correct
2 Correct 1056 ms 1496 KB Output is correct
3 Correct 502 ms 23632 KB Output is correct
4 Correct 664 ms 1568 KB Output is correct
5 Correct 832 ms 17208 KB Output is correct
6 Correct 812 ms 1456 KB Output is correct
7 Correct 1052 ms 1624 KB Output is correct
8 Correct 830 ms 1600 KB Output is correct
9 Correct 1020 ms 36000 KB Output is correct
10 Correct 1326 ms 36168 KB Output is correct
11 Correct 1530 ms 61032 KB Output is correct
12 Correct 1160 ms 53544 KB Output is correct
13 Correct 962 ms 1856 KB Output is correct
14 Correct 4 ms 944 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 1760 KB Output is correct
2 Correct 1056 ms 1496 KB Output is correct
3 Correct 502 ms 23632 KB Output is correct
4 Correct 664 ms 1568 KB Output is correct
5 Correct 832 ms 17208 KB Output is correct
6 Correct 812 ms 1456 KB Output is correct
7 Correct 1052 ms 1624 KB Output is correct
8 Correct 830 ms 1600 KB Output is correct
9 Correct 1020 ms 36000 KB Output is correct
10 Correct 1326 ms 36168 KB Output is correct
11 Correct 1530 ms 61032 KB Output is correct
12 Correct 1160 ms 53544 KB Output is correct
13 Correct 962 ms 1856 KB Output is correct
14 Correct 4 ms 944 KB Output is correct
15 Correct 962 ms 1600 KB Output is correct
16 Correct 774 ms 1760 KB Output is correct
17 Correct 670 ms 1352 KB Output is correct
18 Correct 778 ms 17608 KB Output is correct
19 Correct 916 ms 1768 KB Output is correct
20 Correct 912 ms 18240 KB Output is correct
21 Correct 762 ms 1960 KB Output is correct
22 Correct 490 ms 1856 KB Output is correct
23 Correct 1066 ms 44224 KB Output is correct
24 Correct 1396 ms 44048 KB Output is correct
25 Correct 1540 ms 74928 KB Output is correct
26 Correct 1318 ms 63824 KB Output is correct
27 Correct 920 ms 1960 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 1760 KB Output is correct
2 Correct 1056 ms 1496 KB Output is correct
3 Correct 502 ms 23632 KB Output is correct
4 Correct 664 ms 1568 KB Output is correct
5 Correct 832 ms 17208 KB Output is correct
6 Correct 812 ms 1456 KB Output is correct
7 Correct 1052 ms 1624 KB Output is correct
8 Correct 830 ms 1600 KB Output is correct
9 Correct 1020 ms 36000 KB Output is correct
10 Correct 1326 ms 36168 KB Output is correct
11 Correct 1530 ms 61032 KB Output is correct
12 Correct 1160 ms 53544 KB Output is correct
13 Correct 962 ms 1856 KB Output is correct
14 Correct 4 ms 944 KB Output is correct
15 Correct 962 ms 1600 KB Output is correct
16 Correct 774 ms 1760 KB Output is correct
17 Correct 670 ms 1352 KB Output is correct
18 Correct 778 ms 17608 KB Output is correct
19 Correct 916 ms 1768 KB Output is correct
20 Correct 912 ms 18240 KB Output is correct
21 Correct 762 ms 1960 KB Output is correct
22 Correct 490 ms 1856 KB Output is correct
23 Correct 1066 ms 44224 KB Output is correct
24 Correct 1396 ms 44048 KB Output is correct
25 Correct 1540 ms 74928 KB Output is correct
26 Correct 1318 ms 63824 KB Output is correct
27 Correct 920 ms 1960 KB Output is correct
28 Incorrect 532 ms 852 KB Wrong Answer [2]
29 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 924 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -