oj.uz

Submission #259689

# Submission time Handle Problem Language Result Execution time Memory
259689 2020-08-08T09:49:50 Z mjkocijan Two Transportations (JOI19_transportations) C++14
58 / 100
 1606 ms 75248 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
#define MAXN 2020
#define pb push_back
#define INF 1001001001LL

namespace {

int N;
//int variable_example[500000];
int cnt;
vector<ii> g[MAXN];
int dist[MAXN];
set<ii> q;
int getA, getB, getCnt = 0;
int biobr = 0;
unordered_map<ll, int> mp;
int las = 0;

}  // namespace

void obradiA()
{
	ii cu = *q.begin();
	q.erase(q.begin());
	las = cu.X;
	biobr++;//cout<<cu.X<<'/'<<cu.Y<<endl;
	
	for (ii i: g[cu.Y]) {
		if (dist[i.X] > dist[cu.Y] + i.Y) {
			if (q.count({dist[i.X], i.X})) q.erase({dist[i.X], i.X});
			dist[i.X] = dist[cu.Y] + i.Y;
			q.insert({dist[i.X], i.X});
		}
	}
	
	if (q.empty()) {
		if (biobr == N) return;
		SendA(0);
		return;
		for (int i = 0; i < 9; i++) SendA(0);
		for (int i = 0; i < 11; i++) SendA(0);
		return;
	}
	
	ii nx = *q.begin();
	nx.X = nx.X - cu.X;
	if (mp.count(nx.X * INF + nx.Y)) {
	//if (mp[nx.Y] > 1) {
		SendA(0);
		return;
	}
	SendA(1);
	mp[nx.X * INF + nx.Y] = 1;
	//mp[nx.Y]++;
	for (int i = 0; i < 9; i++) SendA(nx.X & (1 << i));
	for (int i = 0; i < 11; i++) SendA(nx.Y & (1 << i));
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::N = N;
  if (N == 1) return;
  for (int i = 0; i < A; ++i) {
    //variable_example[i] = U[i] + V[i] - C[i];
    g[U[i]].pb({V[i], C[i]});
    g[V[i]].pb({U[i], C[i]});
  }
  for (int i = 0; i < N; i++) {
  	dist[i] = INF;
  }
  dist[0] = 0;
  q.insert({0, 0});
  obradiA();
}

int waitA = 1;

void ReceiveA(bool x) {//cout<<x<<' '<<biobr<<endl;
	if (waitA && x) {
		waitA = 0;
		return;
	}
	if (waitA && !x) {
		obradiA();
		return;
	}
  if (getCnt == 0) {
  	getA = getB = 0;
  }
  getCnt++;
  if (getCnt <= 9) {
  	if (x)
  		getA |= (1 << (getCnt - 1));
  }
  else if (x)
  	getB |= (1 << (getCnt - 1 - 9));
  
  if (getCnt == 9 + 11) { //cout << getA <<'.' << getB<<endl;
  getA += las;//cout << getA <<'.' << getB<<endl;
  mp[getA * INF + getB] = 1;
  //mp[getB]++;
  waitA = 1;
  	if (dist[getB] > getA) {
  		if (q.count({dist[getB], getB})) q.erase({dist[getB], getB});
  		dist[getB] = getA;
  		q.insert({dist[getB], getB});
  	}
  	getCnt = 0;
  	obradiA();
  }
  /*++cnt;
  if (cnt < 58000) {
    SendA(x);
    ++cnt;
  }*/
}

std::vector<int> Answer() {
	if (N == 1) return vector<int>(1, 0);
	
  std::vector<int> ans(N);
  for (int k = 0; k < N; ++k) {
  	ans[k] = dist[k];
    //ans[k] = variable_example[k];
  }
  return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
#define MAXN 2020
#define pb push_back
#define INF 1001001001LL

namespace {

int N;
int cnt;
vector<ii> g[MAXN];
int dist[MAXN];
set<ii> q;
int getA, getB, getCnt = 0;
int biobr = 0;
unordered_map<ll, int> mp;
int las = 0;

bool FunctionExample(bool P) {
  return !P;
}

}  // namespace

void obradiB()
{
	ii cu = *q.begin();
	q.erase(q.begin());
	las = cu.X;
	biobr++;//cout<<cu.X<<'|'<<cu.Y<<endl;
	
	for (ii i: g[cu.Y]) {
		if (dist[i.X] > dist[cu.Y] + i.Y) {
			if (q.count({dist[i.X], i.X})) q.erase({dist[i.X], i.X});
			dist[i.X] = dist[cu.Y] + i.Y;
			q.insert({dist[i.X], i.X});
		}
	}
	
	if (q.empty()) {
		if (biobr == N) return;
		SendB(0);
		return;
		for (int i = 0; i < 9; i++) SendB(0);
		for (int i = 0; i < 11; i++) SendB(0);
		return;
	}
	
	//if (cu.Y == 0) return;
	
	ii nx = *q.begin();
	nx.X = nx.X - cu.X;
	if (mp.count(nx.X * INF + nx.Y)) {
	//if (mp[nx.Y] > 1) {
		SendB(0);
		return;
	}
	SendB(1);
	
	mp[nx.X * INF + nx.Y] = 1;
	//mp[nx.Y]++;
	for (int i = 0; i < 9; i++) SendB(nx.X & (1 << i));
	for (int i = 0; i < 11; i++) SendB(nx.Y & (1 << i));
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  ::N = N;
  if (N == 1) return;
  for (int i = 0; i < B; ++i) {
    //variable_example[i] = U[i] + V[i] - C[i];
    g[S[i]].pb({T[i], D[i]});
    g[T[i]].pb({S[i], D[i]});
  }
  for (int i = 0; i < N; i++) {
  	dist[i] = INF;
  }
  dist[0] = 0;
  q.insert({0, 0});
  obradiB();
}

int waitB = 1;

void ReceiveB(bool y) {//cout<<y<<' '<<biobr<<".\n";
	if (waitB && y) {
		waitB = 0;
		return;
	}
	if (waitB && !y) {
		obradiB();
		return;
	}
  if (getCnt == 0) {
  	getA = getB = 0;
  }
  getCnt++;
  if (getCnt <= 9) {
  	if (y)
  		getA |= (1 << (getCnt - 1));
  }
  else if (y)
  	getB |= (1 << (getCnt - 1 - 9));
  
  if (getCnt == 9 + 11) {  //cout << getA<<','<<getB<<endl;
  	getA += las;//cout << getA<<','<<getB<<endl;
  	mp[getA * INF + getB] = 1;
  	//mp[getB]++;
  	waitB = 1;
  	if (dist[getB] > getA) {
  		if (q.count({dist[getB], getB})) q.erase({dist[getB], getB});
  		dist[getB] = getA;
  		q.insert({dist[getB], getB});
  	}
  	getCnt = 0;
  	obradiB();
  }
}

Compilation message

Azer.cpp:16:5: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
 int cnt;
     ^~~

Baijan.cpp:24:6: warning: 'bool {anonymous}::FunctionExample(bool)' defined but not used [-Wunused-function]
 bool FunctionExample(bool P) {
      ^~~~~~~~~~~~~~~
Baijan.cpp:15:5: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
 int cnt;
     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 2592 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 692 ms 2296 KB Output is correct
4 Correct 1006 ms 20136 KB Output is correct
5 Correct 43 ms 2048 KB Output is correct
6 Correct 1250 ms 4848 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 790 ms 2216 KB Output is correct
3 Incorrect 590 ms 1268 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 1872 KB Output is correct
2 Correct 710 ms 1792 KB Output is correct
3 Correct 1031 ms 23736 KB Output is correct
4 Correct 780 ms 2416 KB Output is correct
5 Correct 1080 ms 17464 KB Output is correct
6 Correct 434 ms 2024 KB Output is correct
7 Correct 856 ms 2168 KB Output is correct
8 Correct 832 ms 2488 KB Output is correct
9 Correct 672 ms 36448 KB Output is correct
10 Correct 682 ms 36176 KB Output is correct
11 Correct 1208 ms 61152 KB Output is correct
12 Correct 1062 ms 54128 KB Output is correct
13 Correct 596 ms 2272 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 1872 KB Output is correct
2 Correct 710 ms 1792 KB Output is correct
3 Correct 1031 ms 23736 KB Output is correct
4 Correct 780 ms 2416 KB Output is correct
5 Correct 1080 ms 17464 KB Output is correct
6 Correct 434 ms 2024 KB Output is correct
7 Correct 856 ms 2168 KB Output is correct
8 Correct 832 ms 2488 KB Output is correct
9 Correct 672 ms 36448 KB Output is correct
10 Correct 682 ms 36176 KB Output is correct
11 Correct 1208 ms 61152 KB Output is correct
12 Correct 1062 ms 54128 KB Output is correct
13 Correct 596 ms 2272 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct
15 Correct 816 ms 2152 KB Output is correct
16 Correct 908 ms 1864 KB Output is correct
17 Correct 638 ms 1880 KB Output is correct
18 Correct 1148 ms 17600 KB Output is correct
19 Correct 1130 ms 2136 KB Output is correct
20 Correct 1158 ms 18232 KB Output is correct
21 Correct 1044 ms 2024 KB Output is correct
22 Correct 1180 ms 2040 KB Output is correct
23 Correct 830 ms 44016 KB Output is correct
24 Correct 828 ms 44304 KB Output is correct
25 Correct 1606 ms 75248 KB Output is correct
26 Correct 1252 ms 64704 KB Output is correct
27 Correct 722 ms 2040 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 1872 KB Output is correct
2 Correct 710 ms 1792 KB Output is correct
3 Correct 1031 ms 23736 KB Output is correct
4 Correct 780 ms 2416 KB Output is correct
5 Correct 1080 ms 17464 KB Output is correct
6 Correct 434 ms 2024 KB Output is correct
7 Correct 856 ms 2168 KB Output is correct
8 Correct 832 ms 2488 KB Output is correct
9 Correct 672 ms 36448 KB Output is correct
10 Correct 682 ms 36176 KB Output is correct
11 Correct 1208 ms 61152 KB Output is correct
12 Correct 1062 ms 54128 KB Output is correct
13 Correct 596 ms 2272 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct
15 Correct 816 ms 2152 KB Output is correct
16 Correct 908 ms 1864 KB Output is correct
17 Correct 638 ms 1880 KB Output is correct
18 Correct 1148 ms 17600 KB Output is correct
19 Correct 1130 ms 2136 KB Output is correct
20 Correct 1158 ms 18232 KB Output is correct
21 Correct 1044 ms 2024 KB Output is correct
22 Correct 1180 ms 2040 KB Output is correct
23 Correct 830 ms 44016 KB Output is correct
24 Correct 828 ms 44304 KB Output is correct
25 Correct 1606 ms 75248 KB Output is correct
26 Correct 1252 ms 64704 KB Output is correct
27 Correct 722 ms 2040 KB Output is correct
28 Correct 1022 ms 2544 KB Output is correct
29 Incorrect 641 ms 1232 KB Wrong Answer [2]
30 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 758 ms 2592 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 692 ms 2296 KB Output is correct
4 Correct 1006 ms 20136 KB Output is correct
5 Correct 43 ms 2048 KB Output is correct
6 Correct 1250 ms 4848 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 790 ms 2216 KB Output is correct
9 Incorrect 590 ms 1268 KB Wrong Answer [2]
10 Halted 0 ms 0 KB -