oj.uz

답안 #126614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126614 2019-07-08T07:41:08 Z dndhk Two Transportations (JOI19_transportations) C++14
0 / 100
 1644 ms 61072 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();
    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) {
 	::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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 706 ms 904 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 438 ms 924 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 704 ms 1560 KB Output is correct
2 Correct 586 ms 1352 KB Output is correct
3 Correct 1370 ms 23584 KB Output is correct
4 Correct 548 ms 1880 KB Output is correct
5 Correct 1424 ms 17248 KB Output is correct
6 Correct 942 ms 1608 KB Output is correct
7 Correct 760 ms 1800 KB Output is correct
8 Correct 540 ms 1632 KB Output is correct
9 Correct 1644 ms 36024 KB Output is correct
10 Correct 986 ms 35888 KB Output is correct
11 Correct 1268 ms 61072 KB Output is correct
12 Correct 1460 ms 53424 KB Output is correct
13 Correct 1048 ms 1504 KB Output is correct
14 Incorrect 5 ms 992 KB Output isn't correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 704 ms 1560 KB Output is correct
2 Correct 586 ms 1352 KB Output is correct
3 Correct 1370 ms 23584 KB Output is correct
4 Correct 548 ms 1880 KB Output is correct
5 Correct 1424 ms 17248 KB Output is correct
6 Correct 942 ms 1608 KB Output is correct
7 Correct 760 ms 1800 KB Output is correct
8 Correct 540 ms 1632 KB Output is correct
9 Correct 1644 ms 36024 KB Output is correct
10 Correct 986 ms 35888 KB Output is correct
11 Correct 1268 ms 61072 KB Output is correct
12 Correct 1460 ms 53424 KB Output is correct
13 Correct 1048 ms 1504 KB Output is correct
14 Incorrect 5 ms 992 KB Output isn't correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 704 ms 1560 KB Output is correct
2 Correct 586 ms 1352 KB Output is correct
3 Correct 1370 ms 23584 KB Output is correct
4 Correct 548 ms 1880 KB Output is correct
5 Correct 1424 ms 17248 KB Output is correct
6 Correct 942 ms 1608 KB Output is correct
7 Correct 760 ms 1800 KB Output is correct
8 Correct 540 ms 1632 KB Output is correct
9 Correct 1644 ms 36024 KB Output is correct
10 Correct 986 ms 35888 KB Output is correct
11 Correct 1268 ms 61072 KB Output is correct
12 Correct 1460 ms 53424 KB Output is correct
13 Correct 1048 ms 1504 KB Output is correct
14 Incorrect 5 ms 992 KB Output isn't correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 706 ms 904 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -