oj.uz

Submission #126695

# Submission time Handle Problem Language Result Execution time Memory
126695 2019-07-08T09:28:58 Z dndhk Two Transportations (JOI19_transportations) C++14
62 / 100
 2041 ms 85416 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(){
        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;
            }
        }
    }

    void make_ans(){
      
        //cout<<n<<" "<<d<<" "<<mx<<endl<<endl;
        //cout<<n2<<" "<<d2<<endl<<endl;
        if(d<d2){
            dist[n] = d;
            vst[n] = true;
        }else{
            dist[n2] = d2;
            n = n2; d = d2;
            vst[n] = true;
        }
        
        calc();

        if(finish){
          Answer();
          return;
        }
        //cout<<n<<" "<<d<<endl;
        //cout<<n<<" "<<d<<" "<<mx<<endl;
        for(int i=0; i<LOG_N; i++){
          SendA((bool)(n%2)); n/=2;
        }
        d-=mx;
        d = min(d, (1<<LOG_D)-1);
        for(int i=0; i<LOG_D; i++){
          SendA((bool)(d%2)); d/=2;
        }
        n = d = cnt = 0;
        two = 1;
        mx = 0;
        for(int i=0; i<N; i++){
            if(!vst[i]) continue;
            mx = max(mx, dist[i]);
        }
    }

}   

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;
    for(int i=0; i<N; i++){
        if(!vst[i]) continue;
        mx = max(mx, dist[i]);
    }
    calc();
   // cout<<finish;
    if(finish){
      Answer();
      return;
    }
}


void ReceiveA(bool x) {
    if(cnt<LOG_N){
        n += (int)x * two;
        two*=2;
    }else if(cnt < LOG_D+LOG_N){
        d += (int)x * two;
        two*=2;
    }
    cnt++;
    if(cnt==LOG_N){
      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 two = 1;
    bool finish = false;
    void calc2(){
        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;
          }
        }
        n = 0;
        d = INF+1;
        for(int i=0; i<N; i++){
            if(vst[i])  continue;
            if(dist[i] < d){
              d = dist[i];
              n = i;
            }
        }
    }
    void make_ans2(){
    	vst[n] = true;
    	dist[n] = d;
 		//cout<<"*"<<n<<" "<<d<<" "<<mx<<endl<<endl;
	 	mx = 0;
	 	for(int i=0; i<N; i++){
	 		if(!vst[i])	continue;
	 		mx = max(mx, dist[i]);
	 	}
    	calc2();
 		//cout<<"*"<<n<<" "<<d<<" "<<mx<<endl;
    	int n2 = n, d2 = d;
    	for(int i=0; i<LOG_N; i++){
 			SendB((bool)(n2%2)); n2/=2;
	 	}
	 	d2-=mx;
	 	d2 = min(d2, (1<<LOG_D)-1);
	 	for(int i=0; i<LOG_D; i++){
	 		SendB((bool)(d2%2)); d2/=2;
	 	}
	 	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;
 	for(int i=0; i<N; i++){
 		if(!vst[i])	continue;
 		mx = max(mx, dist[i]);
 	}
 	calc2();
 	int n2 = n, d2 = d;
 	d2-=mx;
 	//cout<<"*"<<n<<" "<<d<<" "<<endl;
 	for(int i=0; i<LOG_N; i++){
 		SendB((bool)(n2%2)); n2/=2;
 	}
 	d2 = min(d2, (1<<LOG_D)-1);
 	for(int i=0; i<LOG_D; i++){
 		SendB((bool)(d2%2)); d2/=2;
 	}
 	cnt = 0;
}

void ReceiveB(bool y) {
	if(cnt==0){
		n = d = 0;
		two = 1;
	}
	//cout<<"#"<<cnt<<" "<<y<<endl;
	if(cnt<LOG_N){
		n += (int)y*two;
	}else if(cnt<LOG_D+LOG_N){
		d += (int)y*two;
	}
	two*=2;
	cnt++;
	if(cnt==LOG_N){
		two = 1;
	}
	if(cnt==LOG_D+LOG_N){
	 	d+=mx;
		make_ans2();
	}
}

Compilation message

Azer.cpp: In function 'void {anonymous}::calc()':
Azer.cpp:41: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:40: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:38:10: warning: '{anonymous}::finish' defined but not used [-Wunused-variable]
     bool finish = false;
          ^~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1504 KB Output is correct
2 Incorrect 584 ms 860 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1144 KB Output is correct
2 Correct 396 ms 1312 KB Output is correct
3 Correct 714 ms 23592 KB Output is correct
4 Correct 652 ms 1656 KB Output is correct
5 Correct 740 ms 17496 KB Output is correct
6 Correct 708 ms 1616 KB Output is correct
7 Correct 562 ms 1896 KB Output is correct
8 Correct 633 ms 1872 KB Output is correct
9 Correct 854 ms 36088 KB Output is correct
10 Correct 940 ms 36048 KB Output is correct
11 Correct 1416 ms 61280 KB Output is correct
12 Correct 1054 ms 53672 KB Output is correct
13 Correct 596 ms 1632 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1144 KB Output is correct
2 Correct 396 ms 1312 KB Output is correct
3 Correct 714 ms 23592 KB Output is correct
4 Correct 652 ms 1656 KB Output is correct
5 Correct 740 ms 17496 KB Output is correct
6 Correct 708 ms 1616 KB Output is correct
7 Correct 562 ms 1896 KB Output is correct
8 Correct 633 ms 1872 KB Output is correct
9 Correct 854 ms 36088 KB Output is correct
10 Correct 940 ms 36048 KB Output is correct
11 Correct 1416 ms 61280 KB Output is correct
12 Correct 1054 ms 53672 KB Output is correct
13 Correct 596 ms 1632 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct
15 Correct 928 ms 1560 KB Output is correct
16 Correct 836 ms 1672 KB Output is correct
17 Correct 708 ms 1488 KB Output is correct
18 Correct 1014 ms 17664 KB Output is correct
19 Correct 638 ms 1552 KB Output is correct
20 Correct 960 ms 17960 KB Output is correct
21 Correct 784 ms 1656 KB Output is correct
22 Correct 784 ms 1528 KB Output is correct
23 Correct 1430 ms 43632 KB Output is correct
24 Correct 1256 ms 43688 KB Output is correct
25 Correct 1542 ms 75352 KB Output is correct
26 Correct 1470 ms 64496 KB Output is correct
27 Correct 716 ms 1704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 1144 KB Output is correct
2 Correct 396 ms 1312 KB Output is correct
3 Correct 714 ms 23592 KB Output is correct
4 Correct 652 ms 1656 KB Output is correct
5 Correct 740 ms 17496 KB Output is correct
6 Correct 708 ms 1616 KB Output is correct
7 Correct 562 ms 1896 KB Output is correct
8 Correct 633 ms 1872 KB Output is correct
9 Correct 854 ms 36088 KB Output is correct
10 Correct 940 ms 36048 KB Output is correct
11 Correct 1416 ms 61280 KB Output is correct
12 Correct 1054 ms 53672 KB Output is correct
13 Correct 596 ms 1632 KB Output is correct
14 Correct 4 ms 1344 KB Output is correct
15 Correct 928 ms 1560 KB Output is correct
16 Correct 836 ms 1672 KB Output is correct
17 Correct 708 ms 1488 KB Output is correct
18 Correct 1014 ms 17664 KB Output is correct
19 Correct 638 ms 1552 KB Output is correct
20 Correct 960 ms 17960 KB Output is correct
21 Correct 784 ms 1656 KB Output is correct
22 Correct 784 ms 1528 KB Output is correct
23 Correct 1430 ms 43632 KB Output is correct
24 Correct 1256 ms 43688 KB Output is correct
25 Correct 1542 ms 75352 KB Output is correct
26 Correct 1470 ms 64496 KB Output is correct
27 Correct 716 ms 1704 KB Output is correct
28 Correct 896 ms 1832 KB Output is correct
29 Correct 824 ms 1528 KB Output is correct
30 Correct 1412 ms 42072 KB Output is correct
31 Correct 826 ms 1512 KB Output is correct
32 Correct 1158 ms 37448 KB Output is correct
33 Correct 1088 ms 1616 KB Output is correct
34 Correct 996 ms 1752 KB Output is correct
35 Correct 950 ms 1872 KB Output is correct
36 Correct 1310 ms 49328 KB Output is correct
37 Correct 1370 ms 49104 KB Output is correct
38 Correct 2041 ms 85416 KB Output is correct
39 Correct 1606 ms 78448 KB Output is correct
40 Correct 1067 ms 1760 KB Output is correct

Subtask #7
0 / 16.0

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