oj.uz

Submission #132122

# Submission time Handle Problem Language Result Execution time Memory
132122 2019-07-18T10:27:42 Z hamzqq9 Two Transportations (JOI19_transportations) C++14
0 / 100
 618 ms 976 KB 
#include "Azer.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 1000000000
#define N 200005
#define MOD 998244353
#define KOK 700   
using namespace std;

int nA;
vector<vector<ii>> vA;
vector<int> visA,from0A;

void sendA(int val) {

  for(int i=10;i>=0;i--) {

    SendA((val>>i)&1);

  }

}

void spA() {

  vector<int> prv=visA;

  visA=vector<int>(nA,-1);

  priority_queue<ii> q;

  q.push({0,0});

  while(!q.empty()) {

    ii top=q.top();

    q.pop();

    if(visA[top.nd]!=-1) continue;

    visA[top.nd]=-top.st;

    if(!top.nd) {

      for(int i=1;i<nA;i++) {

        if(from0A[i]!=inf) {

          q.push({top.st-from0A[i],i});

        }
 
      }

    }
    else {

      for(auto x:vA[top.nd]) {

        q.push({top.st-x.nd,x.st});

      }

    }

  }

  vector<ii> tbsA;

  for(int i=0;i<nA;i++) {

    if(visA[i]==-1 || visA[i]!=prv[i]) {

      for(int j=0;j<nA;j++) {

        if(visA[j]!=-1 && visA[j]!=prv[j]) {

          tbsA.pb({j,visA[j]});

        }

      }

      break ;
 
    }

  }

  if(sz(tbsA)) {

    sendA(sz(tbsA));

    for(auto x:tbsA) {

      sendA(x.st);
      sendA(x.nd);

    }

  }

}

void InitA(int n, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {

  nA=n;

  vA=vector<vector<ii>>(nA);
  from0A=vector<int>(nA,inf);
  visA=vector<int>(nA,-1);

  for(int i=0;i<A;i++) {

    if(U[i]>V[i]) swap(U[i],V[i]);

    if(!U[i]) {

      umin(from0A[V[i]],C[i]);

      continue ;

    }

    vA[U[i]].pb({V[i],C[i]});
    vA[V[i]].pb({U[i],C[i]});

  }

}

int cntA;
int itA;
int bA,cA;
int okA[3]={0};
int oktA;

void ReceiveA(bool x) {

  if(!okA[0]) {

    okA[0]=1;

    spA();

  }
  else {

    if(!oktA) {

      itA<<=1;
      itA+=x;

      ++cntA;

      if(cntA==11) {

        oktA=1;
        cntA=0;

      }

    }
    else if(!okA[1]) {

      bA<<=1;
      bA+=x;

      cntA++;

      if(cntA==11) {

        cntA=0;
        okA[1]=1;

      }
  
    }
    else {

      cA<<=1;
      cA+=x;

      cntA++;

      if(cntA==11) {

        cntA=0;
        okA[1]=okA[2]=0;

        umin(from0A[bA],cA);
        bA=cA=0;
        itA--;

        if(!itA) {

          oktA=0;

          spA();

        }

      }

    }

  }

}

std::vector<int> Answer() {

  return visA;

}

#include "Baijan.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 1000000000
#define N 200005
#define MOD 998244353
#define KOK 700		
using namespace std;

int nB;
vector<vector<ii>> vB;
vector<int> visB,from0B;

void sendB(int val) {

  for(int i=10;i>=0;i--) {

    SendB((val>>i)&1);

  }

}

void spB() {

  vector<int> prv=visB;

  visB=vector<int>(nB,-1);

  priority_queue<ii> q;

  q.push({0,0});

  while(!q.empty()) {

    ii top=q.top();

    q.pop();

    if(visB[top.nd]!=-1) continue;

    visB[top.nd]=-top.st;

    if(!top.nd) {

      for(int i=1;i<nB;i++) {

        if(from0B[i]!=inf) {

          q.push({top.st-from0B[i],i});

        }
 
      }

    }
    else {

      for(auto x:vB[top.nd]) {

        q.push({top.st-x.nd,x.st});

      }

    }

  }

  vector<ii> tbsB;

  for(int i=0;i<nB;i++) {

    if(visB[i]==-1 || visB[i]!=prv[i]) {

      for(int j=0;j<nB;j++) {

        if(visB[j]!=-1 && visB[j]!=prv[j]) {

          tbsB.pb({j,visB[j]});

        }

      }

      break ;
 
    }

  }

  if(sz(tbsB)) {

    sendB(sz(tbsB));

    for(auto x:tbsB) {

      sendB(x.st);
      sendB(x.nd);

    }

  }

}

void InitB(int n, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) {
	
	nB=n;

  vB=vector<vector<ii>>(nB);
  from0B=vector<int>(nB,inf);
  visB=vector<int>(nB,-1);

  for(int i=0;i<B;i++) {

    if(S[i]>T[i]) swap(S[i],T[i]);

    if(!S[i]) {

      umin(from0B[T[i]],D[i]);

      continue ;

    }

    vB[S[i]].pb({T[i],D[i]});
    vB[T[i]].pb({S[i],D[i]});

  }

  SendB(1);

}

int itB;
int cntB;
int bB,cB;
int okB[3]={1,0,0};
int oktB;

void ReceiveB(bool y) {
  
  if(!okB[0]) {

    okB[0]=1;

  }
  else {

  	if(!oktB) {

      itB<<=1;
      itB+=y;

      ++cntB;

      if(cntB==11) {

        oktB=1;
        cntB=0;

      }

    }
    else if(!okB[1]) {

      bB<<=1;
      bB+=y;

      cntB++;

      if(cntB==11) {

        cntB=0;
        okB[1]=1;

      }
  
    }
    else {

      cB<<=1;
      cB+=y;

      cntB++;

      if(cntB==11) {

        cntB=0;
        okB[1]=okB[2]=0;

        umin(from0B[bB],cB);
        bB=cB=0;

        itB--;

        if(!itB) {

        	spB();
        	oktB=0;

        }

      }

    }

  }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 956 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 856 KB Output is correct
2 Incorrect 618 ms 936 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 16.0

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