Submission #99353

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
99353	2019-03-02 21:18:56	TadijaSebez	Highway Tolls (IOI18_highway)	C++11	100 / 100	519 ms	16564 KiB

highway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=100050;
ll dist;
vector<pair<int,int>> E[N];
vector<int> I[N];
int d[N],f[N];
void AddEdge(int u, int v, int id){ E[u].pb(mp(v,id));E[v].pb(mp(u,id));}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B)
{
  int m=U.size();
  int top=m-1,bot=0,mid,ans;
  vector<int> use(m,0);
  dist=ask(use);
  while(top>=bot)
  {
    mid=top+bot>>1;
    use.clear();use.resize(m);
    for(int i=0;i<=mid;i++) use[i]=1;
    if(ask(use)==dist) bot=mid+1;
    else ans=mid,top=mid-1;
  }
  for(int i=ans+1;i<m;i++) AddEdge(U[i],V[i],i);
  queue<int> q;q.push(U[ans]);q.push(V[ans]);
  d[U[ans]]=d[V[ans]]=1;
  f[U[ans]]=1;f[V[ans]]=2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
highway.cpp: In lambda function:
highway.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
highway.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=mid;i<vs.size();i++) if(vs[i]!=bad) for(int id:I[vs[i]]) use[id]=1;
                  ~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:28:27: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  queue<int> q;q.push(U[ans]);q.push(V[ans]);
                           ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31