oj.uz

Submission #132145

# Submission time Handle Problem Language Result Execution time Memory
132145 2019-07-18T10:52:52 Z ekrem Two Transportations (JOI19_transportations) C++14
0 / 100
 3000 ms 14840 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;

namespace {
int n, m, say, su, crp = 1, onceki, yol, node, bekle, amk = 1, d[MAXN], u[MAXN];
vi x, y, z;
ii mn;

void yolla(int x, int y){
	for(int i = 1; i <= y; i++){
		SendA(x%2);
		x /= 2;
	}
}

void yap(){
	mn = mp(inf, 0);
	for(int i = 0; i < n; i++)if(!u[i])d[i] = inf;
	for(int i = 0; i < m; i++){
		if(!u[x[i]] and !u[y[i]])continue;
		d[x[i]] = min(d[x[i]], d[y[i]] + z[i]);
		d[y[i]] = min(d[y[i]], d[x[i]] + z[i]);
	}
	for(int i = 0; i < n; i++)
		if(!u[i])
			mn = min(mn, mp(d[i], i));
	// cout << "A da buldum " << mn.st << " cunk " << onceki << endl;
	if(mn.st >= inf)
		yolla(510, 9);
	else
		yolla(mn.st - onceki, 9);
}

void kendi(){
	yolla(mn.nd, 11);
}


}

void InitA(int nn, int mm, vi xx, vi yy, vi zz) {n=nn;m=mm;x=xx;y=yy;z=zz;
	u[0] = 1;
	yap();
}

void ReceiveA(bool xx) {
	su += crp*xx;
	crp *= 2;
	say++;
	if(!bekle and say == 9){
		yol = onceki + ((su == 510)?inf:su);
		su = 0;crp = 1;say = 0;
		// cout << "A ya geldi " << yol << endl;
		if(mn.st < yol){
			onceki = d[mn.nd] = mn.st;
			u[mn.nd] = 1;
			amk++;
			if(amk >= n)return;
			kendi();
			yap();
		} else{
			bekle = 1;
		}
	}
	if(bekle and say == 11){
		node = su;
		su = 0;crp = 1;say = 0;bekle = 0;
		// cout << "A ya node geldi " << node << endl;
		
		u[node] = 1;
		onceki = d[node] = yol;
		amk++;
		if(amk >= n)return;
		yap();
	}
}

void sonsuz(int x){
	sonsuz(x+x);
}

vi Answer() {
	vi ans(n);
	for (int k = 0; k < n; ++k){
		if(d[k] >= inf)
			sonsuz(1);
		if(d[k] < 0)assert(0);
		ans[k] = d[k];
	}
	return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;

namespace {
int n, m, say, su, crp = 1, onceki, yol, node, bekle = 1, d[MAXN], u[MAXN];
vi x, y, z;
ii mn;

void yolla(int x, int y){
	for(int i = 1; i <= y; i++){
		SendB(x%2);
		x /= 2;
	}
}

void yap(){
	mn = mp(inf, 0);
	for(int i = 0; i < n; i++)if(!u[i])d[i] = inf;
	for(int i = 0; i < m; i++){
		if(!u[x[i]] and !u[y[i]])continue;
		d[x[i]] = min(d[x[i]], d[y[i]] + z[i]);
		d[y[i]] = min(d[y[i]], d[x[i]] + z[i]);
	}
	for(int i = 0; i < n; i++)
		if(!u[i])
			mn = min(mn, mp(d[i], i));
	// cout << "B da buldum " << mn.st << " cunk " << onceki << endl;
	if(mn.st >= inf)
		yolla(510, 9);
	else
		yolla(mn.st - onceki, 9);
}

void kendi(){
	yolla(mn.nd, 11);
}

}

void InitB(int nn, int mm, vi xx, vi yy, vi zz) {n=nn;m=mm;x=xx;y=yy;z=zz;
	u[0] = 1;
}

void ReceiveB(bool xx) {
	su += crp*xx;
	crp *= 2;
	say++;
	if(bekle and say == 9){
		yol = onceki + ((su == 510)?inf:su);
		su = 0;crp = 1;say = 0;
		// cout << "B ye geldi " << yol << endl;

		yap();

		if(mn.st <= yol){
			onceki = d[mn.nd] = mn.st;
			u[mn.nd] = 1;
			kendi();
			bekle = 1;
		} else{
			bekle = 0;
		}
	}
	if(!bekle and say == 11){
		node = su;
		su = 0;crp = 1;say = 0;bekle = 1;
		// cout << "B ya node geldi " << node << endl;
		u[node] = 1;
		onceki = d[node] = yol;
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 1352 KB Output is correct
2 Execution timed out 3000 ms 484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 1528 KB Output is correct
2 Execution timed out 3000 ms 544 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1304 KB Output is correct
2 Correct 538 ms 1376 KB Output is correct
3 Execution timed out 3000 ms 14840 KB
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1304 KB Output is correct
2 Correct 538 ms 1376 KB Output is correct
3 Execution timed out 3000 ms 14840 KB
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1304 KB Output is correct
2 Correct 538 ms 1376 KB Output is correct
3 Execution timed out 3000 ms 14840 KB
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 1352 KB Output is correct
2 Execution timed out 3000 ms 484 KB Time limit exceeded
3 Halted 0 ms 0 KB -