oj.uz

Submission #126621

# Submission time Handle Problem Language Result Execution time Memory
126621 2019-07-08T07:45:14 Z dndhk Two Transportations (JOI19_transportations) C++14
38 / 100
 1440 ms 61392 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 2000000000
#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 = 20;
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 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 = (1<<LOG_D)-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(){
      bool b = true;
        //cout<<n<<" "<<d<<endl;
        //cout<<n2<<" "<<d2<<endl<<endl;
        if(d<d2){
            dist[n] = d;
            vst[n] = true;
        }else{
            b = false;
            dist[n2] = d2;
            n = n2; d = d2;
            vst[n] = true;
        }
        calc();
        if(finish){
          Answer();
          return;
        }
        if(b){
          n = d = cnt = 0;
          two = 1;
          SendA(1);
          return;
        }
        SendA(0);
        //cout<<n<<" "<<d<<endl;
        for(int i=0; i<LOG_N; i++){
          SendA((bool)(n%2)); n/=2;
        }for(int i=0; i<LOG_D; i++){
          SendA((bool)(d%2)); d/=2;
        }
        n = d = cnt = 0;
        two = 1;
    }

}   

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] = (1<<LOG_D)-1;
    }
    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){
        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 = 20;

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 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 = (1<<LOG_D)-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<<" "<<endl;
    	calc2();
 		//cout<<"*"<<n<<" "<<d<<" "<<endl;
    	int n2 = n, d2 = d;
    	for(int i=0; i<LOG_N; i++){
 			SendB((bool)(n2%2)); n2/=2;
	 	}
	 	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] = (1<<LOG_D)-1;
 	calc2();
 	int n2 = n, d2 = d;
 	//cout<<"*"<<n<<" "<<d<<" "<<endl;
 	for(int i=0; i<LOG_N; i++){
 		SendB((bool)(n2%2)); n2/=2;
 	}
 	for(int i=0; i<LOG_D; i++){
 		SendB((bool)(d2%2)); d2/=2;
 	}
 	cnt = 0;
}

void ReceiveB(bool y) {
	if(cnt==0){
		if(y==1){
			make_ans2();
		}else{
			n = d = 0;
			two = 1;
			cnt++;
		}
		return;
	}
	//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+1){
		two = 1;
	}
	if(cnt==LOG_D+LOG_N+1){
		make_ans2();
	}
}

Compilation message

Azer.cpp: In function 'void {anonymous}::calc()':
Azer.cpp:40: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:39: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:37: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 673 ms 960 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1248 KB Output is correct
2 Incorrect 387 ms 916 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 1720 KB Output is correct
2 Correct 534 ms 1728 KB Output is correct
3 Correct 1068 ms 23616 KB Output is correct
4 Correct 552 ms 1600 KB Output is correct
5 Correct 1190 ms 17168 KB Output is correct
6 Correct 804 ms 1592 KB Output is correct
7 Correct 590 ms 1496 KB Output is correct
8 Correct 848 ms 1656 KB Output is correct
9 Correct 1026 ms 35832 KB Output is correct
10 Correct 752 ms 35752 KB Output is correct
11 Correct 1254 ms 61392 KB Output is correct
12 Correct 1440 ms 53488 KB Output is correct
13 Correct 578 ms 1680 KB Output is correct
14 Correct 4 ms 1248 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 1720 KB Output is correct
2 Correct 534 ms 1728 KB Output is correct
3 Correct 1068 ms 23616 KB Output is correct
4 Correct 552 ms 1600 KB Output is correct
5 Correct 1190 ms 17168 KB Output is correct
6 Correct 804 ms 1592 KB Output is correct
7 Correct 590 ms 1496 KB Output is correct
8 Correct 848 ms 1656 KB Output is correct
9 Correct 1026 ms 35832 KB Output is correct
10 Correct 752 ms 35752 KB Output is correct
11 Correct 1254 ms 61392 KB Output is correct
12 Correct 1440 ms 53488 KB Output is correct
13 Correct 578 ms 1680 KB Output is correct
14 Correct 4 ms 1248 KB Output is correct
15 Correct 890 ms 1392 KB Output is correct
16 Incorrect 504 ms 796 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 1720 KB Output is correct
2 Correct 534 ms 1728 KB Output is correct
3 Correct 1068 ms 23616 KB Output is correct
4 Correct 552 ms 1600 KB Output is correct
5 Correct 1190 ms 17168 KB Output is correct
6 Correct 804 ms 1592 KB Output is correct
7 Correct 590 ms 1496 KB Output is correct
8 Correct 848 ms 1656 KB Output is correct
9 Correct 1026 ms 35832 KB Output is correct
10 Correct 752 ms 35752 KB Output is correct
11 Correct 1254 ms 61392 KB Output is correct
12 Correct 1440 ms 53488 KB Output is correct
13 Correct 578 ms 1680 KB Output is correct
14 Correct 4 ms 1248 KB Output is correct
15 Correct 890 ms 1392 KB Output is correct
16 Incorrect 504 ms 796 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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