oj.uz

Submission #135789

# Submission time Handle Problem Language Result Execution time Memory
135789 2019-07-24T11:12:47 Z dndhk Two Transportations (JOI19_transportations) C++14
100 / 100
 2094 ms 85288 KB 
#include "Azer.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;
const int LOG_N = 11;
const int LOG_D = 9;
namespace {

    int N;
    vector<pii> gp[MAX_N+1];
    int dist[MAX_N+1];
    int vst[MAX_N+1];
    int n=0, d=0, cnt=0;
    int mx;
    int n2=0, d2=0;
    bool finish = false;
    int two = 1;




    void calc(){
        vst[n] = true;
        mx = 0;
        for(int i=0; i<N; i++){
            if(!vst[i]) continue;
            mx = max(mx, dist[i]);
        }
        for(int i=0; i<gp[n].size(); i++){
          if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){
            dist[gp[n][i].first] = dist[n] + gp[n][i].second;
          }
        }
        n2 = 0;
        d2 = INF+1;
        finish = true;
        for(int i=0; i<N; i++){
            if(!vst[i]) finish = false;
            if(vst[i])  continue;
            if(dist[i] < d2){
              d2 = dist[i];
              n2 = i;
            }
        }
        if(finish){
            Answer();
            return;
        }
        d2 -= mx;
        d2 = min(d2, (1<<9)-1);
        //cout<<"SendA "<<d2<<endl;
        for(int i=0; i<LOG_D; i++){
            SendA((bool)(d2%2)); d2/=2;
        }
    }

    void make_ans(){
        dist[n] = d;
        
        calc();
        n = d = cnt = 0;
        two = 1;
    }

    void send_idx(){
        //cout<<"SendA "<<n2<<endl;
        n = n2;
        for(int i=0; i<LOG_N; i++){
          SendA((bool)(n2%2)); n2/=2;
        }
        calc();
    }
}   

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    ::N = N;
    for (int i = 0; i < A; ++i) {
        gp[U[i]].pb({V[i], C[i]});
        gp[V[i]].pb({U[i], C[i]});
    }
    vst[0] = 1;
    dist[0] = 0;
    for(int i=1; i<N; i++){
        dist[i] = INF;
    }
    mx = 0;
    calc();
}


void ReceiveA(bool x) {
    if(cnt<LOG_D){
        d += (int)x * two;
        two*=2;
    }else if(cnt < LOG_D+LOG_N){
        n += (int)x * two;
        two*=2;
    }
    cnt++;
    if(cnt==LOG_D){
        if(d > 500){
            send_idx();
            n = d = cnt = 0;
        }
        two = 1;
    }
    if(cnt==LOG_D+LOG_N){
        d+=mx;
        make_ans();
    }
}

vector<int> Answer() {
    vector<int> ans(N);
    for(int i=0; i<N; i++){
        ans[i] = dist[i];
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;

const int MAX_N = 2000;
const int LOG_N = 11;
const int LOG_D = 9;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

namespace {
	int N;
    vector<pii> gp[MAX_N+1];
    int dist[MAX_N+1];
    int vst[MAX_N+1];
    int mx;
    int n=0, d=0, cnt=0;
    int n2=0, d2=0;
    int two = 1;
    bool finish = false;

    void calc2(){
    	mx = 0;
    	for(int i=0; i<N; i++){
	 		if(!vst[i])	continue;
	 		mx = max(mx, dist[i]);
	 	}
        for(int i=0; i<gp[n].size(); i++){
          if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){
            dist[gp[n][i].first] = dist[n] + gp[n][i].second;
          }
        }
        n2 = 0;
        d2 = INF+1;
        for(int i=0; i<N; i++){
            if(vst[i])  continue;
            if(dist[i] < d2){
              d2 = dist[i];
              n2 = i;
            }
        }
    }
    void make_ans2(){
    	vst[n] = true;
    	dist[n] = d;
 		//cout<<"*"<<n<<" "<<d<<" "<<mx<<endl<<endl;
	 	mx = 0;
    	calc2();
 		//cout<<"*"<<n<<" "<<d<<" "<<mx<<endl;
	 	cnt = 0;
    }
} 

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	if(N==1)	return;
 	::N = N;
 	for(int i=0; i<B; i++){
 		gp[S[i]].pb({T[i], D[i]});
 		gp[T[i]].pb({S[i], D[i]});
 	}
 	vst[0] = true;
 	for(int i=1; i<N; i++)	dist[i] = INF;
 	mx = 0;
 	calc2();
 	cnt = 0;
}

void ReceiveB(bool y) {
	if(cnt==0){
		n = d = 0;
		two = 1;
	}
	//cout<<"#"<<cnt<<" "<<y<<endl;
	if(cnt<LOG_D){
		d += (int)y*two;
	}else if(cnt<LOG_D+LOG_N){
		n += (int)y*two;
	}
	two*=2;
	cnt++;
	if(cnt==LOG_D){
		two = 1;
		d += mx;
		if(d<d2){
			//cout<<"SendB 255"<<endl;
			for(int i=0; i<LOG_D; i++){
				SendB(1);
			}
		}else{
		 	d2-=mx;
		 	//cout<<"SendB "<<d2<<endl;
		 	for(int i=0; i<LOG_D; i++){
		 		SendB((bool)(d2%2)); d2/=2;
		 	}
		 	//cout<<"SendB "<<n2<<endl;
			n = n2;
			vst[n] = true;
	    	for(int i=0; i<LOG_N; i++){
	 			SendB((bool)(n2%2)); n2/=2;
		 	}
		 	calc2();
		 	cnt = 0;
		}
	}
	if(cnt==LOG_D+LOG_N){
		make_ans2();
	}
}

Compilation message

Azer.cpp: In function 'void {anonymous}::calc()':
Azer.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<gp[n].size(); i++){
                      ~^~~~~~~~~~~~~

Baijan.cpp: In function 'void {anonymous}::calc2()':
Baijan.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<gp[n].size(); i++){
                      ~^~~~~~~~~~~~~
Baijan.cpp: At global scope:
Baijan.cpp:39:10: warning: '{anonymous}::finish' defined but not used [-Wunused-variable]
     bool finish = false;
          ^~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 1504 KB Output is correct
2 Correct 3 ms 1504 KB Output is correct
3 Correct 1010 ms 1512 KB Output is correct
4 Correct 1276 ms 20120 KB Output is correct
5 Correct 78 ms 1480 KB Output is correct
6 Correct 1058 ms 4416 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1248 KB Output is correct
2 Correct 1152 ms 1896 KB Output is correct
3 Correct 1176 ms 1848 KB Output is correct
4 Correct 1524 ms 55200 KB Output is correct
5 Correct 1454 ms 48280 KB Output is correct
6 Correct 124 ms 1376 KB Output is correct
7 Correct 1374 ms 48208 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 1672 KB Output is correct
2 Correct 8 ms 1248 KB Output is correct
3 Correct 1000 ms 1480 KB Output is correct
4 Correct 928 ms 1568 KB Output is correct
5 Correct 1166 ms 1760 KB Output is correct
6 Correct 1176 ms 1664 KB Output is correct
7 Correct 970 ms 1952 KB Output is correct
8 Correct 816 ms 1608 KB Output is correct
9 Correct 1177 ms 1488 KB Output is correct
10 Correct 1002 ms 1520 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 1104 KB Output is correct
2 Correct 389 ms 1320 KB Output is correct
3 Correct 618 ms 23584 KB Output is correct
4 Correct 364 ms 1504 KB Output is correct
5 Correct 674 ms 17208 KB Output is correct
6 Correct 522 ms 1376 KB Output is correct
7 Correct 468 ms 1664 KB Output is correct
8 Correct 456 ms 1776 KB Output is correct
9 Correct 788 ms 35992 KB Output is correct
10 Correct 840 ms 35808 KB Output is correct
11 Correct 1016 ms 61296 KB Output is correct
12 Correct 976 ms 53512 KB Output is correct
13 Correct 370 ms 1760 KB Output is correct
14 Correct 4 ms 968 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 1104 KB Output is correct
2 Correct 389 ms 1320 KB Output is correct
3 Correct 618 ms 23584 KB Output is correct
4 Correct 364 ms 1504 KB Output is correct
5 Correct 674 ms 17208 KB Output is correct
6 Correct 522 ms 1376 KB Output is correct
7 Correct 468 ms 1664 KB Output is correct
8 Correct 456 ms 1776 KB Output is correct
9 Correct 788 ms 35992 KB Output is correct
10 Correct 840 ms 35808 KB Output is correct
11 Correct 1016 ms 61296 KB Output is correct
12 Correct 976 ms 53512 KB Output is correct
13 Correct 370 ms 1760 KB Output is correct
14 Correct 4 ms 968 KB Output is correct
15 Correct 616 ms 1512 KB Output is correct
16 Correct 420 ms 1784 KB Output is correct
17 Correct 632 ms 1552 KB Output is correct
18 Correct 824 ms 17432 KB Output is correct
19 Correct 634 ms 1656 KB Output is correct
20 Correct 626 ms 17736 KB Output is correct
21 Correct 604 ms 1672 KB Output is correct
22 Correct 528 ms 1672 KB Output is correct
23 Correct 840 ms 43944 KB Output is correct
24 Correct 886 ms 43696 KB Output is correct
25 Correct 1228 ms 75096 KB Output is correct
26 Correct 1052 ms 64216 KB Output is correct
27 Correct 528 ms 1696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 1104 KB Output is correct
2 Correct 389 ms 1320 KB Output is correct
3 Correct 618 ms 23584 KB Output is correct
4 Correct 364 ms 1504 KB Output is correct
5 Correct 674 ms 17208 KB Output is correct
6 Correct 522 ms 1376 KB Output is correct
7 Correct 468 ms 1664 KB Output is correct
8 Correct 456 ms 1776 KB Output is correct
9 Correct 788 ms 35992 KB Output is correct
10 Correct 840 ms 35808 KB Output is correct
11 Correct 1016 ms 61296 KB Output is correct
12 Correct 976 ms 53512 KB Output is correct
13 Correct 370 ms 1760 KB Output is correct
14 Correct 4 ms 968 KB Output is correct
15 Correct 616 ms 1512 KB Output is correct
16 Correct 420 ms 1784 KB Output is correct
17 Correct 632 ms 1552 KB Output is correct
18 Correct 824 ms 17432 KB Output is correct
19 Correct 634 ms 1656 KB Output is correct
20 Correct 626 ms 17736 KB Output is correct
21 Correct 604 ms 1672 KB Output is correct
22 Correct 528 ms 1672 KB Output is correct
23 Correct 840 ms 43944 KB Output is correct
24 Correct 886 ms 43696 KB Output is correct
25 Correct 1228 ms 75096 KB Output is correct
26 Correct 1052 ms 64216 KB Output is correct
27 Correct 528 ms 1696 KB Output is correct
28 Correct 642 ms 1768 KB Output is correct
29 Correct 696 ms 1360 KB Output is correct
30 Correct 1036 ms 41712 KB Output is correct
31 Correct 528 ms 1640 KB Output is correct
32 Correct 1008 ms 37288 KB Output is correct
33 Correct 812 ms 1664 KB Output is correct
34 Correct 644 ms 1872 KB Output is correct
35 Correct 582 ms 1688 KB Output is correct
36 Correct 1074 ms 49104 KB Output is correct
37 Correct 1232 ms 49016 KB Output is correct
38 Correct 1674 ms 85288 KB Output is correct
39 Correct 1236 ms 78424 KB Output is correct
40 Correct 882 ms 1792 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 1504 KB Output is correct
2 Correct 3 ms 1504 KB Output is correct
3 Correct 1010 ms 1512 KB Output is correct
4 Correct 1276 ms 20120 KB Output is correct
5 Correct 78 ms 1480 KB Output is correct
6 Correct 1058 ms 4416 KB Output is correct
7 Correct 8 ms 1248 KB Output is correct
8 Correct 1152 ms 1896 KB Output is correct
9 Correct 1176 ms 1848 KB Output is correct
10 Correct 1524 ms 55200 KB Output is correct
11 Correct 1454 ms 48280 KB Output is correct
12 Correct 124 ms 1376 KB Output is correct
13 Correct 1374 ms 48208 KB Output is correct
14 Correct 1092 ms 1672 KB Output is correct
15 Correct 8 ms 1248 KB Output is correct
16 Correct 1000 ms 1480 KB Output is correct
17 Correct 928 ms 1568 KB Output is correct
18 Correct 1166 ms 1760 KB Output is correct
19 Correct 1176 ms 1664 KB Output is correct
20 Correct 970 ms 1952 KB Output is correct
21 Correct 816 ms 1608 KB Output is correct
22 Correct 1177 ms 1488 KB Output is correct
23 Correct 1002 ms 1520 KB Output is correct
24 Correct 518 ms 1104 KB Output is correct
25 Correct 389 ms 1320 KB Output is correct
26 Correct 618 ms 23584 KB Output is correct
27 Correct 364 ms 1504 KB Output is correct
28 Correct 674 ms 17208 KB Output is correct
29 Correct 522 ms 1376 KB Output is correct
30 Correct 468 ms 1664 KB Output is correct
31 Correct 456 ms 1776 KB Output is correct
32 Correct 788 ms 35992 KB Output is correct
33 Correct 840 ms 35808 KB Output is correct
34 Correct 1016 ms 61296 KB Output is correct
35 Correct 976 ms 53512 KB Output is correct
36 Correct 370 ms 1760 KB Output is correct
37 Correct 4 ms 968 KB Output is correct
38 Correct 616 ms 1512 KB Output is correct
39 Correct 420 ms 1784 KB Output is correct
40 Correct 632 ms 1552 KB Output is correct
41 Correct 824 ms 17432 KB Output is correct
42 Correct 634 ms 1656 KB Output is correct
43 Correct 626 ms 17736 KB Output is correct
44 Correct 604 ms 1672 KB Output is correct
45 Correct 528 ms 1672 KB Output is correct
46 Correct 840 ms 43944 KB Output is correct
47 Correct 886 ms 43696 KB Output is correct
48 Correct 1228 ms 75096 KB Output is correct
49 Correct 1052 ms 64216 KB Output is correct
50 Correct 528 ms 1696 KB Output is correct
51 Correct 642 ms 1768 KB Output is correct
52 Correct 696 ms 1360 KB Output is correct
53 Correct 1036 ms 41712 KB Output is correct
54 Correct 528 ms 1640 KB Output is correct
55 Correct 1008 ms 37288 KB Output is correct
56 Correct 812 ms 1664 KB Output is correct
57 Correct 644 ms 1872 KB Output is correct
58 Correct 582 ms 1688 KB Output is correct
59 Correct 1074 ms 49104 KB Output is correct
60 Correct 1232 ms 49016 KB Output is correct
61 Correct 1674 ms 85288 KB Output is correct
62 Correct 1236 ms 78424 KB Output is correct
63 Correct 882 ms 1792 KB Output is correct
64 Correct 1378 ms 2096 KB Output is correct
65 Correct 1645 ms 46784 KB Output is correct
66 Correct 1752 ms 41112 KB Output is correct
67 Correct 1024 ms 2016 KB Output is correct
68 Correct 1076 ms 1824 KB Output is correct
69 Correct 2094 ms 83376 KB Output is correct
70 Correct 1852 ms 68064 KB Output is correct
71 Correct 1250 ms 9024 KB Output is correct
72 Correct 1062 ms 2384 KB Output is correct