oj.uz

Submission #132371

# Submission time Handle Problem Language Result Execution time Memory
132371 2019-07-18T18:39:19 Z sebinkim Two Transportations (JOI19_transportations) C++14
62 / 100
 1966 ms 85448 KB 
#include <bits/stdc++.h>

#include "Azer.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 9;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n, z;
}

static void sendint(int x, int l) { x = min(x, (1 << l) - 1); for(; l--; ) SendA((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
	chk[p] = 1; D[p] = d; z = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check()
{
	int p, d;
	
	for(; !Q.empty(); Q.pop()){
		tie(d, p) = Q.top(); d = -d;
		if(!chk[p] && d == D[p]) break;
	}
	
	if(Q.empty()) return;
	
	_st = 0;
	
	tie(d, p) = Q.top(); d = -d;
	
	sendint(p, ID);
	sendint(d - z, DIST);
}

void InitA(int N, int A, vector <int> U, vector <int> V, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<A; i++){
		G[U[i]].emplace_back(V[i], C[i]);
		G[V[i]].emplace_back(U[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = 1e9;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
	check();
}

void ReceiveA(bool x)
{
	if(!_st){
		if(!x){
			int d, p;
			tie(d, p) = Q.top();
			d = -d; Q.pop();
			apply(p, d); check();
		}
		else _st = 1;
	}
	else{
		_val = _val << 1 | x; _cnt ++;
	
		if(_cnt == ID + DIST){
			int p = _val >> DIST;
			int d = z + (_val & ((1 << DIST) - 1));
			_val = 0; _cnt = 0; _st = 0;
			apply(p, d); check();
		}
	}
}

vector <int> Answer() { return D; }
#include <bits/stdc++.h>

#include "Baijan.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 9;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n, z;
}

static void sendint(int x, int l) { x = min(x, (1 << l) - 1); for(; l--; ) SendB((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
	chk[p] = 1; D[p] = d; z = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check(int pa, int da)
{
	int p, d, pb, db;
	
	for(; !Q.empty(); Q.pop()){
		tie(db, pb) = Q.top(); db = -db;
		if(!chk[pb] && D[pb] == db) break;
	}
	
	tie(db, pb) = Q.top(); db = -db;
	
	if(da < db){
		p = pa, d = da;
		SendB(0);
	}
	else{
		p = pb, d = db; Q.pop();
		SendB(1);
		sendint(p, ID);
		sendint(d - z, DIST);
	}
	
	apply(p, d);
}

void InitB(int N, int B, vector <int> S, vector<int> T, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<B; i++){
		G[S[i]].emplace_back(T[i], C[i]);
		G[T[i]].emplace_back(S[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = 1e9;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
}

void ReceiveB(bool y)
{
	_val = _val << 1 | y; _cnt ++;
	
	if(_cnt == ID + DIST){
		int p = _val >> DIST;
		int d = z + (_val & ((1 << DIST) - 1));
		_val = 0; _cnt = 0;
		check(p, d);
	}
}

Compilation message

Baijan.cpp:17:6: warning: '{anonymous}::_st' defined but not used [-Wunused-variable]
  int _st, _val, _cnt;
      ^~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1248 KB Output is correct
2 Incorrect 403 ms 976 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 1512 KB Output is correct
2 Correct 366 ms 1272 KB Output is correct
3 Correct 726 ms 23656 KB Output is correct
4 Correct 651 ms 1488 KB Output is correct
5 Correct 844 ms 17184 KB Output is correct
6 Correct 566 ms 1600 KB Output is correct
7 Correct 530 ms 1568 KB Output is correct
8 Correct 542 ms 1704 KB Output is correct
9 Correct 740 ms 35912 KB Output is correct
10 Correct 936 ms 36096 KB Output is correct
11 Correct 1086 ms 61168 KB Output is correct
12 Correct 990 ms 53664 KB Output is correct
13 Correct 602 ms 1680 KB Output is correct
14 Correct 4 ms 1192 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 1512 KB Output is correct
2 Correct 366 ms 1272 KB Output is correct
3 Correct 726 ms 23656 KB Output is correct
4 Correct 651 ms 1488 KB Output is correct
5 Correct 844 ms 17184 KB Output is correct
6 Correct 566 ms 1600 KB Output is correct
7 Correct 530 ms 1568 KB Output is correct
8 Correct 542 ms 1704 KB Output is correct
9 Correct 740 ms 35912 KB Output is correct
10 Correct 936 ms 36096 KB Output is correct
11 Correct 1086 ms 61168 KB Output is correct
12 Correct 990 ms 53664 KB Output is correct
13 Correct 602 ms 1680 KB Output is correct
14 Correct 4 ms 1192 KB Output is correct
15 Correct 620 ms 1832 KB Output is correct
16 Correct 288 ms 1712 KB Output is correct
17 Correct 488 ms 1768 KB Output is correct
18 Correct 1002 ms 17552 KB Output is correct
19 Correct 588 ms 1760 KB Output is correct
20 Correct 864 ms 18064 KB Output is correct
21 Correct 532 ms 1504 KB Output is correct
22 Correct 606 ms 1640 KB Output is correct
23 Correct 876 ms 43744 KB Output is correct
24 Correct 1138 ms 43992 KB Output is correct
25 Correct 1451 ms 74936 KB Output is correct
26 Correct 1290 ms 64608 KB Output is correct
27 Correct 360 ms 1864 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 1512 KB Output is correct
2 Correct 366 ms 1272 KB Output is correct
3 Correct 726 ms 23656 KB Output is correct
4 Correct 651 ms 1488 KB Output is correct
5 Correct 844 ms 17184 KB Output is correct
6 Correct 566 ms 1600 KB Output is correct
7 Correct 530 ms 1568 KB Output is correct
8 Correct 542 ms 1704 KB Output is correct
9 Correct 740 ms 35912 KB Output is correct
10 Correct 936 ms 36096 KB Output is correct
11 Correct 1086 ms 61168 KB Output is correct
12 Correct 990 ms 53664 KB Output is correct
13 Correct 602 ms 1680 KB Output is correct
14 Correct 4 ms 1192 KB Output is correct
15 Correct 620 ms 1832 KB Output is correct
16 Correct 288 ms 1712 KB Output is correct
17 Correct 488 ms 1768 KB Output is correct
18 Correct 1002 ms 17552 KB Output is correct
19 Correct 588 ms 1760 KB Output is correct
20 Correct 864 ms 18064 KB Output is correct
21 Correct 532 ms 1504 KB Output is correct
22 Correct 606 ms 1640 KB Output is correct
23 Correct 876 ms 43744 KB Output is correct
24 Correct 1138 ms 43992 KB Output is correct
25 Correct 1451 ms 74936 KB Output is correct
26 Correct 1290 ms 64608 KB Output is correct
27 Correct 360 ms 1864 KB Output is correct
28 Correct 841 ms 1560 KB Output is correct
29 Correct 1032 ms 1760 KB Output is correct
30 Correct 1320 ms 42056 KB Output is correct
31 Correct 852 ms 1560 KB Output is correct
32 Correct 1616 ms 37696 KB Output is correct
33 Correct 760 ms 1680 KB Output is correct
34 Correct 760 ms 1808 KB Output is correct
35 Correct 1120 ms 2072 KB Output is correct
36 Correct 896 ms 49160 KB Output is correct
37 Correct 1578 ms 49152 KB Output is correct
38 Correct 1966 ms 85448 KB Output is correct
39 Correct 1616 ms 78520 KB Output is correct
40 Correct 844 ms 2416 KB Output is correct

Subtask #7
0 / 16.0

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