oj.uz

Submission #239864

# Submission time Handle Problem Language Result Execution time Memory
239864 2020-06-17T12:24:05 Z b00n0rp Two Transportations (JOI19_transportations) C++17
38 / 100
 1822 ms 61712 KB 
#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))

namespace {

	int N;
	vpii adj[2005];
	int dist[2005],done[2005];
	int count = 1;
	int pend;
	int verA,distA,verB,distB;
	PQD(pii) pq;

	void send(int x, int len){
		FORD(i,len-1,0) SendA((x>>i)&1);
	}	

	void refresh(){
		while(pq.size()){
			int u = pq.top().S;
			pq.pop();
			for(auto v:adj[u]){
				if(dist[v.F] > dist[u]+v.S){
					dist[v.F] = dist[u]+v.S;
					pq.push({dist[v.F],v.F});
				}
			}
		}
	}

	void do_next(){
		if(count == N) return;
		count++;
		refresh();
		int u = -1;
		REP(i,N){
			if(done[i]) continue;
			if(u == -1 or dist[i] < dist[u]) u = i;
		}
		pend = 31;
		verA = u;
		distA = dist[u];
		verB = 0;
		distB = 0;
		// cerr << "Azer sends: " << verA << "-" << distA << endl;
		// REP(i,N){
		// 	cerr << i << " - " << dist[i] << endl;
		// }
		send(verA,11);
		send(distA,20);
	}

}  // namespace

void InitA(int N, int A, vi U, vi V, vi C) {
	::N = N;
	REP(i,A){
		adj[U[i]].pb({V[i],C[i]});
		adj[V[i]].pb({U[i],C[i]});
	}
	REP(i,N) dist[i] = (1<<20)-1;
	dist[0] = 0;
	done[0] = 1;
	pq.push({0,0});

	do_next();

}

void ReceiveA(bool x){
	pend--;
	if(pend >= 20){
		verB += ((int) x)*(1<<(pend-20));
	}
	else{
		distB += ((int) x)*(1<<pend);
		if(pend == 0){
			remin(dist[verA],distA);
			remin(dist[verB],distB);
			if(distA < distB){
				done[verA] = 1;
			}
			else{
				done[verB] = 1;
			}
			pq.push({distB,verB});
			do_next();
		}
	}
}

vi Answer() {
  vi vd;
  REP(i,N) vd.pb(dist[i]);
  return vd;
}

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))


namespace {

	int N;
	vpii adj[2005];
	int dist[2005],done[2005];
	int pend = 31;
	int verA,distA,verB,distB;
	PQD(pii) pq;

	void send(int x, int len){
		FORD(i,len-1,0) SendB((x>>i)&1);
	}	

	void refresh(){
		while(pq.size()){
			int u = pq.top().S;
			pq.pop();
			for(auto v:adj[u]){
				if(dist[v.F] > dist[u]+v.S){
					dist[v.F] = dist[u]+v.S;
					pq.push({dist[v.F],v.F});
				}
			}
		}
	}

	void do_next(){
		int u = -1;
		REP(i,N){
			if(done[i]) continue;
			if(u == -1 or dist[i] < dist[u]) u = i;
		}
		verB = u;
		distB = dist[u];

		remin(dist[verA],distA);
		remin(dist[verB],distB);
		if(distA < distB){
			done[verA] = 1;
		}
		else{
			done[verB] = 1;
		}
		pq.push({distA,verA});
		refresh();

		pend = 31;
		verA = 0;
		distA = 0;

		// cerr << "Baijin sends: " << verB << "-" << distB << endl; 
		// REP(i,N){
		// 	cerr << i << " - " << dist[i] << endl;
		// }
		send(verB,11);
		send(distB,20);
	}

}  // namespace

void InitB(int N, int B, vi S, vi T, vi D) {
	::N = N;
	REP(i,B){
		adj[S[i]].pb({T[i],D[i]});
		adj[T[i]].pb({S[i],D[i]});
	}
	REP(i,N) dist[i] = (1<<20)-1;
	dist[0] = 0;
	done[0] = 1;
	pq.push({0,0});
	refresh();
}

void ReceiveB(bool y) {
	pend--;
	if(pend >= 20){
		verA += ((int) y)*(1<<(pend-20));
	}
	else{
		distA += ((int) y)*(1<<pend);
		if(pend == 0){
			do_next();
		}
	}
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1280 KB Output is correct
2 Incorrect 529 ms 768 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 1536 KB Output is correct
2 Correct 1232 ms 1560 KB Output is correct
3 Correct 1100 ms 24312 KB Output is correct
4 Correct 1040 ms 1792 KB Output is correct
5 Correct 1134 ms 17464 KB Output is correct
6 Correct 1094 ms 1792 KB Output is correct
7 Correct 1044 ms 1792 KB Output is correct
8 Correct 1090 ms 1792 KB Output is correct
9 Correct 1342 ms 36336 KB Output is correct
10 Correct 1392 ms 36832 KB Output is correct
11 Correct 1822 ms 61712 KB Output is correct
12 Correct 1550 ms 54040 KB Output is correct
13 Correct 954 ms 2048 KB Output is correct
14 Correct 18 ms 1536 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 1536 KB Output is correct
2 Correct 1232 ms 1560 KB Output is correct
3 Correct 1100 ms 24312 KB Output is correct
4 Correct 1040 ms 1792 KB Output is correct
5 Correct 1134 ms 17464 KB Output is correct
6 Correct 1094 ms 1792 KB Output is correct
7 Correct 1044 ms 1792 KB Output is correct
8 Correct 1090 ms 1792 KB Output is correct
9 Correct 1342 ms 36336 KB Output is correct
10 Correct 1392 ms 36832 KB Output is correct
11 Correct 1822 ms 61712 KB Output is correct
12 Correct 1550 ms 54040 KB Output is correct
13 Correct 954 ms 2048 KB Output is correct
14 Correct 18 ms 1536 KB Output is correct
15 Incorrect 578 ms 896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 1536 KB Output is correct
2 Correct 1232 ms 1560 KB Output is correct
3 Correct 1100 ms 24312 KB Output is correct
4 Correct 1040 ms 1792 KB Output is correct
5 Correct 1134 ms 17464 KB Output is correct
6 Correct 1094 ms 1792 KB Output is correct
7 Correct 1044 ms 1792 KB Output is correct
8 Correct 1090 ms 1792 KB Output is correct
9 Correct 1342 ms 36336 KB Output is correct
10 Correct 1392 ms 36832 KB Output is correct
11 Correct 1822 ms 61712 KB Output is correct
12 Correct 1550 ms 54040 KB Output is correct
13 Correct 954 ms 2048 KB Output is correct
14 Correct 18 ms 1536 KB Output is correct
15 Incorrect 578 ms 896 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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