oj.uz

Submission #239879

# Submission time Handle Problem Language Result Execution time Memory
239879 2020-06-17T12:38:32 Z b00n0rp Two Transportations (JOI19_transportations) C++17
0 / 100
 618 ms 1536 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 global = 0;
	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 = 20;
		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(min(distA-global,(1<<9)-1),9);
	}

}  // 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 >= 9){
		verB += ((int) x)*(1<<(pend-9));
	}
	else{
		distB += ((int) x)*(1<<pend);
		if(pend == 0){
			distB+=global;
			remin(dist[verA],distA);
			remin(dist[verB],distB);
			if(distA < distB){
				done[verA] = 1;
				global = distA;
			}
			else{
				done[verB] = 1;
				pq.push({distB,verB});
				global = distB;
			}
			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 = 20;
	int global = 0;
	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);
		int diff = distB-global;
		if(distA < distB){
			done[verA] = 1;
			global = distA;
			pq.push({distA,verA});
		}
		else{
			done[verB] = 1;
			global = distB;
		}
		refresh();

		pend = 20;
		verA = 0;
		distA = 0;

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

}  // 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 >= 9){
		verA += ((int) y)*(1<<(pend-9));
	}
	else{
		distA += ((int) y)*(1<<pend);
		if(pend == 0){
			distA += global;
			do_next();
		}
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 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 567 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 428 ms 896 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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