oj.uz

Submission #126609

# Submission time Handle Problem Language Result Execution time Memory
126609 2019-07-08T07:38:38 Z dndhk Two Transportations (JOI19_transportations) C++14
0 / 100
 1340 ms 61200 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();
}


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) {
 	::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 511 ms 628 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1576 KB Output is correct
2 Correct 590 ms 1504 KB Output is correct
3 Correct 1278 ms 23624 KB Output is correct
4 Correct 476 ms 1608 KB Output is correct
5 Correct 1288 ms 17344 KB Output is correct
6 Correct 798 ms 1656 KB Output is correct
7 Correct 802 ms 1784 KB Output is correct
8 Correct 830 ms 1480 KB Output is correct
9 Correct 1240 ms 36088 KB Output is correct
10 Correct 668 ms 35872 KB Output is correct
11 Correct 1340 ms 61200 KB Output is correct
12 Correct 1290 ms 53504 KB Output is correct
13 Correct 810 ms 1768 KB Output is correct
14 Incorrect 8 ms 1424 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1576 KB Output is correct
2 Correct 590 ms 1504 KB Output is correct
3 Correct 1278 ms 23624 KB Output is correct
4 Correct 476 ms 1608 KB Output is correct
5 Correct 1288 ms 17344 KB Output is correct
6 Correct 798 ms 1656 KB Output is correct
7 Correct 802 ms 1784 KB Output is correct
8 Correct 830 ms 1480 KB Output is correct
9 Correct 1240 ms 36088 KB Output is correct
10 Correct 668 ms 35872 KB Output is correct
11 Correct 1340 ms 61200 KB Output is correct
12 Correct 1290 ms 53504 KB Output is correct
13 Correct 810 ms 1768 KB Output is correct
14 Incorrect 8 ms 1424 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1576 KB Output is correct
2 Correct 590 ms 1504 KB Output is correct
3 Correct 1278 ms 23624 KB Output is correct
4 Correct 476 ms 1608 KB Output is correct
5 Correct 1288 ms 17344 KB Output is correct
6 Correct 798 ms 1656 KB Output is correct
7 Correct 802 ms 1784 KB Output is correct
8 Correct 830 ms 1480 KB Output is correct
9 Correct 1240 ms 36088 KB Output is correct
10 Correct 668 ms 35872 KB Output is correct
11 Correct 1340 ms 61200 KB Output is correct
12 Correct 1290 ms 53504 KB Output is correct
13 Correct 810 ms 1768 KB Output is correct
14 Incorrect 8 ms 1424 KB Output isn't correct

Subtask #7
0 / 16.0

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