oj.uz

Submission #290423

# Submission time Handle Problem Language Result Execution time Memory
290423 2020-09-03T18:43:56 Z TadijaSebez Two Transportations (JOI19_transportations) C++14
100 / 100
 1890 ms 85976 KB 
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back

namespace{
	const int N=2050;
	const int L=9;
	const int inf=(1<<L)-1;
	vector<pii> E[N];
	int dist[N],n;
	bool was[N];
	void Upd(int x){
		was[x]=1;
		for(auto e:E[x]){
			int v,w;tie(v,w)=e;
			if(!was[v]){
				dist[v]=min(dist[v],dist[x]+w);
			}
		}
	}
	int cnt,X,Y,node,D;
	int w;
	void Send(){
		Y=1e9;
		bool ok=0;
		for(int i=0;i<n;i++)if(!was[i]){
			ok=1;
			if(Y>dist[i]){
				Y=dist[i];
				node=i;
			}
		}
		if(!ok)return;
		Y-=D;
		Y=min(Y,inf);
		for(int i=L-1;~i;i--)SendA(Y>>i&1);
		w=1;
	}
}

void InitA(int n,int a,vi u,vi v,vi w){
	::n=n;
	for(int i=0;i<a;i++)E[u[i]].pb({v[i],w[i]}),E[v[i]].pb({u[i],w[i]});
	for(int i=1;i<n;i++)dist[i]=1e9;
	D=0;
	Upd(0);
	Send();
}

void ReceiveA(bool x){
	X=X*2+x;
	cnt++;
	if(w==1){
		if(cnt==L){
			if(Y<=X){
				for(int i=10;~i;i--)SendA(node>>i&1);
				D+=Y;
				Upd(node);
				Send();
				cnt=0;
				X=0;
			}else{
				D+=X;
				w=2;
				cnt=0;
				X=0;
			}
		}
	}else if(w==2){
		if(cnt==11){
			dist[X]=D;
			Upd(X);
			Send();
			cnt=0;
			X=0;
		}
	}
}

vi Answer(){
	vi ans;
	for(int i=0;i<n;i++)ans.pb(dist[i]);
	return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back

namespace{
	const int N=2050;
	const int L=9;
	const int inf=(1<<L)-1;
	vector<pii> E[N];
	int dist[N],n;
	bool was[N];
	void Upd(int x){
		was[x]=1;
		for(auto e:E[x]){
			int v,w;tie(v,w)=e;
			if(!was[v]){
				dist[v]=min(dist[v],dist[x]+w);
			}
		}
	}
	int cnt,X,Y,node,D;
	int w;
	void Send(){
		Y=1e9;
		bool ok=0;
		for(int i=0;i<n;i++)if(!was[i]){
			ok=1;
			if(Y>dist[i]){
				Y=dist[i];
				node=i;
			}
		}
		if(!ok)return;
		Y-=D;
		Y=min(Y,inf);
		for(int i=L-1;~i;i--)SendB(Y>>i&1);
		w=1;
	}
}

void InitB(int n,int b,vi u,vi v,vi w){
	::n=n;
	for(int i=0;i<b;i++)E[u[i]].pb({v[i],w[i]}),E[v[i]].pb({u[i],w[i]});
	for(int i=1;i<n;i++)dist[i]=1e9;
	D=0;
	Upd(0);
	Send();
}

void ReceiveB(bool y){
	X=X*2+y;
	cnt++;
	if(w==1){
		if(cnt==L){
			if(Y<X){
				for(int i=10;~i;i--)SendB(node>>i&1);
				D+=Y;
				Upd(node);
				Send();
				cnt=0;
				X=0;
			}else{
				D+=X;
				w=2;
				cnt=0;
				X=0;
			}
		}
	}else if(w==2){
		if(cnt==11){
			dist[X]=D;
			Upd(X);
			Send();
			cnt=0;
			X=0;
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 1792 KB Output is correct
2 Correct 2 ms 1304 KB Output is correct
3 Correct 1044 ms 1600 KB Output is correct
4 Correct 1170 ms 20192 KB Output is correct
5 Correct 66 ms 1568 KB Output is correct
6 Correct 940 ms 4464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 1113 ms 1648 KB Output is correct
3 Correct 1098 ms 1856 KB Output is correct
4 Correct 1468 ms 55520 KB Output is correct
5 Correct 1530 ms 48344 KB Output is correct
6 Correct 198 ms 1584 KB Output is correct
7 Correct 1512 ms 48344 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 1720 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 1266 ms 1536 KB Output is correct
4 Correct 1028 ms 1640 KB Output is correct
5 Correct 990 ms 1536 KB Output is correct
6 Correct 1056 ms 1792 KB Output is correct
7 Correct 930 ms 1600 KB Output is correct
8 Correct 1066 ms 1576 KB Output is correct
9 Correct 958 ms 1824 KB Output is correct
10 Correct 1088 ms 1776 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 1576 KB Output is correct
2 Correct 502 ms 1760 KB Output is correct
3 Correct 714 ms 23848 KB Output is correct
4 Correct 432 ms 1536 KB Output is correct
5 Correct 714 ms 17512 KB Output is correct
6 Correct 430 ms 1680 KB Output is correct
7 Correct 578 ms 1688 KB Output is correct
8 Correct 631 ms 1760 KB Output is correct
9 Correct 792 ms 36256 KB Output is correct
10 Correct 854 ms 36320 KB Output is correct
11 Correct 1164 ms 61352 KB Output is correct
12 Correct 924 ms 53856 KB Output is correct
13 Correct 536 ms 1536 KB Output is correct
14 Correct 4 ms 1536 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 1576 KB Output is correct
2 Correct 502 ms 1760 KB Output is correct
3 Correct 714 ms 23848 KB Output is correct
4 Correct 432 ms 1536 KB Output is correct
5 Correct 714 ms 17512 KB Output is correct
6 Correct 430 ms 1680 KB Output is correct
7 Correct 578 ms 1688 KB Output is correct
8 Correct 631 ms 1760 KB Output is correct
9 Correct 792 ms 36256 KB Output is correct
10 Correct 854 ms 36320 KB Output is correct
11 Correct 1164 ms 61352 KB Output is correct
12 Correct 924 ms 53856 KB Output is correct
13 Correct 536 ms 1536 KB Output is correct
14 Correct 4 ms 1536 KB Output is correct
15 Correct 516 ms 1536 KB Output is correct
16 Correct 692 ms 1536 KB Output is correct
17 Correct 718 ms 1456 KB Output is correct
18 Correct 766 ms 17680 KB Output is correct
19 Correct 742 ms 1680 KB Output is correct
20 Correct 686 ms 18024 KB Output is correct
21 Correct 732 ms 1536 KB Output is correct
22 Correct 662 ms 1536 KB Output is correct
23 Correct 912 ms 44032 KB Output is correct
24 Correct 928 ms 44048 KB Output is correct
25 Correct 1374 ms 75264 KB Output is correct
26 Correct 1224 ms 64960 KB Output is correct
27 Correct 733 ms 1920 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 1576 KB Output is correct
2 Correct 502 ms 1760 KB Output is correct
3 Correct 714 ms 23848 KB Output is correct
4 Correct 432 ms 1536 KB Output is correct
5 Correct 714 ms 17512 KB Output is correct
6 Correct 430 ms 1680 KB Output is correct
7 Correct 578 ms 1688 KB Output is correct
8 Correct 631 ms 1760 KB Output is correct
9 Correct 792 ms 36256 KB Output is correct
10 Correct 854 ms 36320 KB Output is correct
11 Correct 1164 ms 61352 KB Output is correct
12 Correct 924 ms 53856 KB Output is correct
13 Correct 536 ms 1536 KB Output is correct
14 Correct 4 ms 1536 KB Output is correct
15 Correct 516 ms 1536 KB Output is correct
16 Correct 692 ms 1536 KB Output is correct
17 Correct 718 ms 1456 KB Output is correct
18 Correct 766 ms 17680 KB Output is correct
19 Correct 742 ms 1680 KB Output is correct
20 Correct 686 ms 18024 KB Output is correct
21 Correct 732 ms 1536 KB Output is correct
22 Correct 662 ms 1536 KB Output is correct
23 Correct 912 ms 44032 KB Output is correct
24 Correct 928 ms 44048 KB Output is correct
25 Correct 1374 ms 75264 KB Output is correct
26 Correct 1224 ms 64960 KB Output is correct
27 Correct 733 ms 1920 KB Output is correct
28 Correct 758 ms 1680 KB Output is correct
29 Correct 706 ms 1616 KB Output is correct
30 Correct 1098 ms 41984 KB Output is correct
31 Correct 722 ms 1536 KB Output is correct
32 Correct 1220 ms 37760 KB Output is correct
33 Correct 754 ms 1600 KB Output is correct
34 Correct 722 ms 1904 KB Output is correct
35 Correct 730 ms 1824 KB Output is correct
36 Correct 1288 ms 49632 KB Output is correct
37 Correct 1130 ms 49456 KB Output is correct
38 Correct 1712 ms 85976 KB Output is correct
39 Correct 1412 ms 78888 KB Output is correct
40 Correct 736 ms 1880 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 1792 KB Output is correct
2 Correct 2 ms 1304 KB Output is correct
3 Correct 1044 ms 1600 KB Output is correct
4 Correct 1170 ms 20192 KB Output is correct
5 Correct 66 ms 1568 KB Output is correct
6 Correct 940 ms 4464 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 1113 ms 1648 KB Output is correct
9 Correct 1098 ms 1856 KB Output is correct
10 Correct 1468 ms 55520 KB Output is correct
11 Correct 1530 ms 48344 KB Output is correct
12 Correct 198 ms 1584 KB Output is correct
13 Correct 1512 ms 48344 KB Output is correct
14 Correct 1172 ms 1720 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct
16 Correct 1266 ms 1536 KB Output is correct
17 Correct 1028 ms 1640 KB Output is correct
18 Correct 990 ms 1536 KB Output is correct
19 Correct 1056 ms 1792 KB Output is correct
20 Correct 930 ms 1600 KB Output is correct
21 Correct 1066 ms 1576 KB Output is correct
22 Correct 958 ms 1824 KB Output is correct
23 Correct 1088 ms 1776 KB Output is correct
24 Correct 504 ms 1576 KB Output is correct
25 Correct 502 ms 1760 KB Output is correct
26 Correct 714 ms 23848 KB Output is correct
27 Correct 432 ms 1536 KB Output is correct
28 Correct 714 ms 17512 KB Output is correct
29 Correct 430 ms 1680 KB Output is correct
30 Correct 578 ms 1688 KB Output is correct
31 Correct 631 ms 1760 KB Output is correct
32 Correct 792 ms 36256 KB Output is correct
33 Correct 854 ms 36320 KB Output is correct
34 Correct 1164 ms 61352 KB Output is correct
35 Correct 924 ms 53856 KB Output is correct
36 Correct 536 ms 1536 KB Output is correct
37 Correct 4 ms 1536 KB Output is correct
38 Correct 516 ms 1536 KB Output is correct
39 Correct 692 ms 1536 KB Output is correct
40 Correct 718 ms 1456 KB Output is correct
41 Correct 766 ms 17680 KB Output is correct
42 Correct 742 ms 1680 KB Output is correct
43 Correct 686 ms 18024 KB Output is correct
44 Correct 732 ms 1536 KB Output is correct
45 Correct 662 ms 1536 KB Output is correct
46 Correct 912 ms 44032 KB Output is correct
47 Correct 928 ms 44048 KB Output is correct
48 Correct 1374 ms 75264 KB Output is correct
49 Correct 1224 ms 64960 KB Output is correct
50 Correct 733 ms 1920 KB Output is correct
51 Correct 758 ms 1680 KB Output is correct
52 Correct 706 ms 1616 KB Output is correct
53 Correct 1098 ms 41984 KB Output is correct
54 Correct 722 ms 1536 KB Output is correct
55 Correct 1220 ms 37760 KB Output is correct
56 Correct 754 ms 1600 KB Output is correct
57 Correct 722 ms 1904 KB Output is correct
58 Correct 730 ms 1824 KB Output is correct
59 Correct 1288 ms 49632 KB Output is correct
60 Correct 1130 ms 49456 KB Output is correct
61 Correct 1712 ms 85976 KB Output is correct
62 Correct 1412 ms 78888 KB Output is correct
63 Correct 736 ms 1880 KB Output is correct
64 Correct 1112 ms 2112 KB Output is correct
65 Correct 1486 ms 46880 KB Output is correct
66 Correct 1572 ms 41136 KB Output is correct
67 Correct 1064 ms 1856 KB Output is correct
68 Correct 1098 ms 1920 KB Output is correct
69 Correct 1890 ms 83432 KB Output is correct
70 Correct 1725 ms 68096 KB Output is correct
71 Correct 992 ms 9168 KB Output is correct
72 Correct 1184 ms 2448 KB Output is correct