Submission #429052

#	Time	Username	Problem	Language	Result	Execution time	Memory
429052		amunduzbaev	Two Transportations (JOI19_transportations)	C++14	100 / 100	1165 ms	58192 KiB

Azer

#include "Azer.h"
#include "bits/stdc++.h" 
using namespace std;

namespace{
	
	//~ #include <ext/pb_ds/assoc_container.hpp>
	//~ #include <ext/pb_ds/tree_policy.hpp>
	//~ using namespace __gnu_pbds;
	//~ template<class T> using oset = tree<T, 
	//~ null_type, less_equal<T>, rb_tree_tag, 
	//~ tree_order_statistics_node_update>;
	 
	#define ff first
	#define ss second
	#define pb push_back
	#define mp make_pair
	#define ub upper_bound
	#define lb lower_bound
	#define sz(x) (int)x.size()
	#define all(x) x.begin(), x.end()
	#define rall(x) x.rbegin(),x.rend()
	#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#define vv vector
	#define mem(arr, v) memset(arr, v, sizeof arr)
	//~ #define int long long
	#define degub(x) cout<<#x<<" : "<<x<<"\n"
	#define GG cout<<"here"<<endl;
	 
	typedef long long ll;
	typedef long double ld;
	typedef pair<int, int> pii; 
	typedef vector<int> vii;
	typedef vector<pii> vpii;
	template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
	template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
	template<int sz> using tut = array<int, sz>;
	//~ void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
		//~ freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
	 
	const int N = 2e5+5;
	const int mod = 1e9+7;
	const ll inf = 1e18;
	const ld Pi = acos(-1);
	 
	#define MULTI 0
	int n, m, k, s, t, q, ans, a; //, a[N];
	int d[N], ligtest, rec, u, w, used[N];
	vpii edges[N];


	void upd(int u){
		used[u] = 1;
		for(auto x : edges[u]) umin(d[x.ff], d[u] + x.ss);
	}

	void send(){
		u = -1, w = mod + 1;
		for(int i=1;i<=n;i++){
			if(used[i]) continue;
			if(d[i] < w) u = i, w = d[u];
		} if(u == -1) return;
		
		//~ cout<<"A\n";
		//~ for(int i=1;i<=n;i++) cout<<d[i]<<" ";
		//~ cout<<"\n";
		
		w -= ligtest;
		umin(w, (1 << 9) - 1);
		//~ cout<<ligtest<<" "<<w<<"\n";
		for(int i=8;~i;i--) SendA(w>>i&1);
		rec = 1;
	} int cost, len;

}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
	n = N, a = A;
	for(int i=0;i<a;i++){
		int a = U[i] + 1, b = V[i] + 1, c = C[i];
		edges[a].pb({b, c}), edges[b].pb({a, c});
	} 
	
	for(int i=1;i<=n;i++) d[i] = mod;
	d[1] = 0;
	upd(1), send();
}

void ReceiveA(bool x) {
	cost = (cost << 1) | x;
	len++;
	if(rec == 1){
		if(len == 9){
			if(w <= cost){
				for(int i=10;~i;i--) SendA(u>>i&1);
				ligtest += w;
				upd(u), send(), len = 0, cost = 0;
			} else rec = 2, ligtest += cost, len = 0, cost = 0;
		} 
	} else if(rec == 2) { 
		if(len == 11){ 
			d[cost] = ligtest;
			upd(cost), send(), len = 0, cost = 0;
		} 
	}
}

vector<int> Answer() {
	vii res;
	for(int i=1;i<=n;i++) res.pb(d[i]);
	return res;
}

Baijan

#include "Baijan.h"
#include "bits/stdc++.h"
using namespace std;

namespace {
	//~ #include <ext/pb_ds/assoc_container.hpp>
	//~ #include <ext/pb_ds/tree_policy.hpp>
	//~ using namespace __gnu_pbds;
	//~ template<class T> using oset = tree<T, 
	//~ null_type, less_equal<T>, rb_tree_tag, 
	//~ tree_order_statistics_node_update>;
	 
	#define ff first
	#define ss second
	#define pb push_back
	#define mp make_pair
	#define ub upper_bound
	#define lb lower_bound
	#define sz(x) (int)x.size()
	#define all(x) x.begin(), x.end()
	#define rall(x) x.rbegin(),x.rend()
	#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#define vv vector
	#define mem(arr, v) memset(arr, v, sizeof arr)
	//~ #define int long long
	#define degub(x) cout<<#x<<" : "<<x<<"\n"
	#define GG cout<<"here"<<endl;
	 
	typedef long long ll;
	typedef long double ld;
	typedef pair<int, int> pii; 
	typedef vector<int> vii;
	typedef vector<pii> vpii;
	template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
	template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
	template<int sz> using tut = array<int, sz>;
	//~ void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
		//~ freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
	 
	const int N = 2e5+5;
	const int mod = 1e9+7;
	const ll inf = 1e18;
	const ld Pi = acos(-1);
	 
	#define MULTI 0
	int n, m, k, s, t, q, ans, a; //, a[N];
	int d[N], ligtest, rec, u, w, used[N];
	vpii edges[N];

	void upd(int u){
		used[u] = 1;
		for(auto x : edges[u]) umin(d[x.ff], d[u] + x.ss);
	}

	void send(){
		u = -1, w = mod + 1;
		for(int i=1;i<=n;i++){
			if(used[i]) continue;
			if(d[i] < w) u = i, w = d[u];
		} if(u == -1) return;
		
		//~ cout<<"B\n";
		//~ for(int i=1;i<=n;i++) cout<<d[i]<<" ";
		//~ cout<<"\n";
		
		w -= ligtest;
		umin(w, (1<<9) - 1);
		//~ cout<<ligtest<<" "<<w<<"\n";
		for(int i=8;~i;i--) SendB(w>>i&1);
		rec = 1;
	} int len, cost;

}

void InitB(int N, int B, vector<int> U, vector<int> T, vector<int> C) {
	a = B, n = N;
	for(int i=0;i<a;i++){
		int a = U[i] + 1, b = T[i] + 1, c = C[i];
		edges[a].pb({b, c}), edges[b].pb({a, c});
	} 
	
	for(int i=1;i<=n;i++) d[i] = mod;
	
	d[1] = 0;
	upd(1), send(); 
}

/*

4 0 7
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7

*/
void ReceiveB(bool x) {
	len++, cost = (cost << 1) | x;
	if(rec == 1){
		if(len == 9){
			if(w < cost){
				for(int i=10;~i;i--) SendB(u>>i&1);
				ligtest += w;
				upd(u), send(); len = 0, cost = 0;
			} else rec = 2, ligtest += cost, len = 0, cost = 0;
		} 
	} else if(rec == 2){
		if(len == 11){
			d[cost] = ligtest;
			upd(cost), send(), len = 0, cost = 0;
		} 
	}
}

Compilation message (stderr)

Azer.cpp:47:24: warning: '{anonymous}::ans' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                        ^~~
Azer.cpp:47:21: warning: '{anonymous}::q' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                     ^
Azer.cpp:47:18: warning: '{anonymous}::t' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                  ^
Azer.cpp:47:15: warning: '{anonymous}::s' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |               ^
Azer.cpp:47:12: warning: '{anonymous}::k' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |            ^
Azer.cpp:47:9: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   47 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |         ^

Baijan.cpp:46:24: warning: '{anonymous}::ans' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                        ^~~
Baijan.cpp:46:21: warning: '{anonymous}::q' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                     ^
Baijan.cpp:46:18: warning: '{anonymous}::t' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |                  ^
Baijan.cpp:46:15: warning: '{anonymous}::s' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |               ^
Baijan.cpp:46:12: warning: '{anonymous}::k' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |            ^
Baijan.cpp:46:9: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   46 |  int n, m, k, s, t, q, ans, a; //, a[N];
      |         ^

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16