Submission #298735

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
298735	2020-09-13T22:05:21 Z	DanerZein	Highway Tolls (IOI18_highway)	C++14	18 / 100	239 ms	10240 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vi;
vector<vi> G;
vector<int> hl;
ll conc[110];
int isq[110];
ll m,a,b,n;
vector<int> bin;
int ed[90010],vis[90010];
void dijkstra(int x){
  memset(vis,0,sizeof vis);
  queue<int> q;
  int e=0;
  q.push(x);
  while(!q.empty()){
    int u=q.front();
    q.pop();
    vis[u]=1;
    for(auto &v:G[u]){
      if(!vis[v.first]){
	bin.push_back(v.second);
	ed[e]=v.first;
	q.push(v.first);
	e++;
      }
    }
  }
}
void line_graph(int u){
  hl.assign(m,0);
  ll w=ask(hl);
  ll no=w/a;
  int l=0,r=m-1;
  ll aux;
  while(r-l>1){
    int mid=(l+r)/2;
    for(int i=0;i<m;i++){
      if(i<mid) hl[i]=1;
      else hl[i]=0;
    }
    aux=ask(hl);
    if(aux==w) l=mid;
    else r=mid;
  }
  answer(l,l+no);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n=N;
  a=A;
  b=B;
  G.resize(N+1);
  for(int i=0;i<U.size();i++){
    int u=U[i],v=V[i];
    G[u].push_back(ii(v,i));
    G[v].push_back(ii(u,i));
  }
  bool sw=0;
  int id=-1;
  for(int i=0;i<N;i++){
    if(G[i].size()>2) sw=1;
    if(G[i].size()==1 and id==-1) id=i;
  }
  m=U.size();
  if(sw==1){
    dijkstra(0);
    hl.assign(m,0);
    /*for(int i=0;i<m;i++){
      cout<<bin[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<m;i++){
      cout<<ed[i]<<" ";
    }
    cout<<endl;*/
    int l=0,r=m-1;
    ll w=ask(hl),aux;
    while(r-l>1){
      int mid=(l+r)/2;
      for(int i=0;i<m;i++){
	if(i<=mid) hl[bin[i]]=0;
	else hl[bin[i]]=1;
      }
      aux=ask(hl);
      if(aux==w) r=mid;
      else l=mid;
      /* for(int i=0;i<m;i++) cout<<hl[i]<<" ";
      cout<<endl;*/
    }
    // cout<<r<<" "<<bin[r]<<" "<<ed[r]<<endl;
    answer(0,ed[r]);
  }
  else{
    line_graph(id);
  }
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i=0;i<U.size();i++){
      |               ~^~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	640 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	1 ms	640 KB	Output is correct
5	Correct	1 ms	640 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	640 KB	Output is correct
9	Correct	1 ms	640 KB	Output is correct
10	Correct	1 ms	640 KB	Output is correct
11	Correct	1 ms	640 KB	Output is correct
12	Correct	1 ms	640 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	768 KB	Output is correct
2	Correct	12 ms	1792 KB	Output is correct
3	Correct	142 ms	10156 KB	Output is correct
4	Correct	136 ms	10136 KB	Output is correct
5	Correct	150 ms	10240 KB	Output is correct
6	Correct	139 ms	10148 KB	Output is correct
7	Correct	128 ms	10084 KB	Output is correct
8	Correct	146 ms	10084 KB	Output is correct
9	Correct	239 ms	10192 KB	Output is correct
10	Correct	225 ms	10072 KB	Output is correct
11	Correct	139 ms	10136 KB	Output is correct
12	Correct	144 ms	10124 KB	Output is correct
13	Correct	141 ms	10132 KB	Output is correct
14	Correct	136 ms	10148 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1280 KB	Output is correct
2	Correct	10 ms	2304 KB	Output is correct
3	Correct	35 ms	3064 KB	Output is correct
4	Correct	106 ms	8496 KB	Output is correct
5	Correct	99 ms	8496 KB	Output is correct
6	Correct	105 ms	8440 KB	Output is correct
7	Correct	108 ms	8572 KB	Output is correct
8	Correct	107 ms	8536 KB	Output is correct
9	Correct	100 ms	8504 KB	Output is correct