Submission #951003

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
951003	2024-03-21T03:59:03 Z	hengliao	Two Transportations (JOI19_transportations)	C++14	62 / 100	954 ms	59480 KB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define F first
#define S second

namespace {

const ll inf=1e9;
ll n;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<ll> ans;
vector<pair<ll, ll>> adj[2005]; 
ll cnt;
ll rcnt;
ll curidx;
ll curdis;
ll pre;

void sendidx(ll tar){
  for(ll i=10;i>=0;i--){
    if(tar&(1LL<<i)){
      SendA(1);
    }
    else{
      SendA(0);
    }
  }
}

void senddis(ll tar){
  for(ll i=8;i>=0;i--){
    if(tar&(1LL<<i)){
      SendA(1);
    }
    else{
      SendA(0);
    }
  }
}

}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
  n=N;
  ans=vector<ll>(n, inf);
  for(ll i=0;i<A;i++){
    adj[U[i]].pb({V[i], C[i]});
    adj[V[i]].pb({U[i], C[i]});
  }
  ans[0]=0;
  cnt=1;
  rcnt=0;
  curidx=0;
  curdis=0;
  pq.push({0, 0});
  pre=0;
  for(auto it:adj[0]){
    ll x=it.F;
    ll y=it.S;
    pq.push({y, x});
  }
  /*
  pair<ll, ll> cur=pq.top();
  sendidx(cur.F);
  senddis(cur.S);
  cnt++;
  */
}

void ReceiveA(bool x) {
  if(rcnt<11){
    curidx*=2;
    if(x) curidx++;
  }
  else{
    curdis*=2;
    if(x) curdis++;
  }
  rcnt++;
  if(rcnt>=20){
    rcnt=0;
    pq.push({curdis+pre, curidx});
    //cerr<<"good "<<curdis+pre<<' '<<curidx<<'\n';
    curidx=0;
    curdis=0;
    while(!pq.empty() && ans[pq.top().S]!=inf){
      pq.pop();
    }
    if(!pq.empty()){
      pair<ll, ll> cur=pq.top();
      ans[cur.S]=cur.F;
      cnt++;
      for(auto it:adj[cur.S]){
        ll x=it.F;
        ll y=it.S;
        pq.push({y+ans[cur.S], x});
      }
      sendidx(cur.S);
      senddis(cur.F-pre);
      pre=cur.F;
    }
    /*else if(cnt<n){
      sendidx(0);
      senddis(255);
    }*/
  }
}

vector<int> Answer() {
  return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define F first
#define S second

namespace {

const ll inf=1e9;
ll n;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<ll> ans;
vector<pair<ll, ll>> adj[2005]; 
ll cnt;
ll rcnt;
ll curidx;
ll curdis;
ll pre;

void sendidx(ll tar){
  for(ll i=10;i>=0;i--){
    if(tar&(1LL<<i)){
      SendB(1);
    }
    else{
      SendB(0);
    }
  }
}

void senddis(ll tar){
  for(ll i=8;i>=0;i--){
    if(tar&(1LL<<i)){
      SendB(1);
    }
    else{
      SendB(0);
    }
  }
}

}  // namespace

void InitB(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
  n=N;
  ans=vector<ll>(n, inf);
  for(ll i=0;i<A;i++){
    adj[U[i]].pb({V[i], C[i]});
    adj[V[i]].pb({U[i], C[i]});
  }
  ans[0]=0;
  cnt=0;
  rcnt=0;
  curidx=0;
  curdis=0;
  //pq.push({0, 0});
  pre=0;
  for(auto it:adj[0]){
  	ll x=it.F;
  	ll y=it.S;
    pq.push({y, x});
  }
  if(pq.empty()){
  	sendidx(0);
  	senddis(511);
  	return;
  }
  pair<ll, ll> cur=pq.top();
  sendidx(cur.S);
  senddis(cur.F);
  cnt++;
}

void ReceiveB(bool x) {
  if(rcnt<11){
    curidx*=2;
    if(x) curidx++;
  }
  else{
    curdis*=2;
    if(x) curdis++;
  }
  rcnt++;
  if(rcnt>=20){
    cnt++;
    rcnt=0;
    ans[curidx]=curdis+pre;
    pre=ans[curidx];
    for(auto it:adj[curidx]){
    	ll x=it.F;
    	ll y=it.S;
    	pq.push({y+ans[curidx], x});
    }
    curidx=0;
    curdis=0;
    while(!pq.empty() && ans[pq.top().S]!=inf){
      pq.pop();
    }
    if(!pq.empty()){
      pair<ll, ll> cur=pq.top();
      sendidx(cur.S);
      senddis(cur.F-pre);
      //pre=cur.F;
    }
    else{
    	sendidx(0);
    	senddis(511);
    }
  }
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	145 ms	460 KB	Execution killed with signal 13
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	664 KB	Output is correct
2	Runtime error	168 ms	548 KB	Execution killed with signal 13
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	193 ms	532 KB	Execution killed with signal 13
2	Halted	0 ms	0 KB	-

Subtask #4

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	229 ms	812 KB	Output is correct
2	Correct	270 ms	784 KB	Output is correct
3	Correct	340 ms	13572 KB	Output is correct
4	Correct	194 ms	844 KB	Output is correct
5	Correct	295 ms	10048 KB	Output is correct
6	Correct	238 ms	664 KB	Output is correct
7	Correct	233 ms	856 KB	Output is correct
8	Correct	249 ms	664 KB	Output is correct
9	Correct	442 ms	26040 KB	Output is correct
10	Correct	427 ms	25724 KB	Output is correct
11	Correct	626 ms	49732 KB	Output is correct
12	Correct	550 ms	48304 KB	Output is correct
13	Correct	211 ms	1088 KB	Output is correct
14	Correct	0 ms	664 KB	Output is correct

Subtask #5

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	229 ms	812 KB	Output is correct
2	Correct	270 ms	784 KB	Output is correct
3	Correct	340 ms	13572 KB	Output is correct
4	Correct	194 ms	844 KB	Output is correct
5	Correct	295 ms	10048 KB	Output is correct
6	Correct	238 ms	664 KB	Output is correct
7	Correct	233 ms	856 KB	Output is correct
8	Correct	249 ms	664 KB	Output is correct
9	Correct	442 ms	26040 KB	Output is correct
10	Correct	427 ms	25724 KB	Output is correct
11	Correct	626 ms	49732 KB	Output is correct
12	Correct	550 ms	48304 KB	Output is correct
13	Correct	211 ms	1088 KB	Output is correct
14	Correct	0 ms	664 KB	Output is correct
15	Correct	290 ms	828 KB	Output is correct
16	Correct	255 ms	664 KB	Output is correct
17	Correct	301 ms	664 KB	Output is correct
18	Correct	377 ms	10548 KB	Output is correct
19	Correct	229 ms	664 KB	Output is correct
20	Correct	406 ms	10420 KB	Output is correct
21	Correct	286 ms	664 KB	Output is correct
22	Correct	295 ms	664 KB	Output is correct
23	Correct	527 ms	28644 KB	Output is correct
24	Correct	542 ms	27848 KB	Output is correct
25	Correct	834 ms	55216 KB	Output is correct
26	Correct	616 ms	50204 KB	Output is correct
27	Correct	254 ms	1136 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	229 ms	812 KB	Output is correct
2	Correct	270 ms	784 KB	Output is correct
3	Correct	340 ms	13572 KB	Output is correct
4	Correct	194 ms	844 KB	Output is correct
5	Correct	295 ms	10048 KB	Output is correct
6	Correct	238 ms	664 KB	Output is correct
7	Correct	233 ms	856 KB	Output is correct
8	Correct	249 ms	664 KB	Output is correct
9	Correct	442 ms	26040 KB	Output is correct
10	Correct	427 ms	25724 KB	Output is correct
11	Correct	626 ms	49732 KB	Output is correct
12	Correct	550 ms	48304 KB	Output is correct
13	Correct	211 ms	1088 KB	Output is correct
14	Correct	0 ms	664 KB	Output is correct
15	Correct	290 ms	828 KB	Output is correct
16	Correct	255 ms	664 KB	Output is correct
17	Correct	301 ms	664 KB	Output is correct
18	Correct	377 ms	10548 KB	Output is correct
19	Correct	229 ms	664 KB	Output is correct
20	Correct	406 ms	10420 KB	Output is correct
21	Correct	286 ms	664 KB	Output is correct
22	Correct	295 ms	664 KB	Output is correct
23	Correct	527 ms	28644 KB	Output is correct
24	Correct	542 ms	27848 KB	Output is correct
25	Correct	834 ms	55216 KB	Output is correct
26	Correct	616 ms	50204 KB	Output is correct
27	Correct	254 ms	1136 KB	Output is correct
28	Correct	294 ms	836 KB	Output is correct
29	Correct	363 ms	792 KB	Output is correct
30	Correct	651 ms	24216 KB	Output is correct
31	Correct	338 ms	784 KB	Output is correct
32	Correct	534 ms	21340 KB	Output is correct
33	Correct	272 ms	868 KB	Output is correct
34	Correct	277 ms	892 KB	Output is correct
35	Correct	258 ms	896 KB	Output is correct
36	Correct	594 ms	32624 KB	Output is correct
37	Correct	599 ms	30344 KB	Output is correct
38	Correct	954 ms	59480 KB	Output is correct
39	Correct	796 ms	56408 KB	Output is correct
40	Correct	292 ms	1512 KB	Output is correct

Subtask #7

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	145 ms	460 KB	Execution killed with signal 13
2	Halted	0 ms	0 KB	-