Submission #579062

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
579062	2022-06-18 11:02:30	ogibogi2004	Highway Tolls (IOI18_highway)	C++14	100 / 100	264 ms	12328 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;
const int MAXN=9e4+6;
const int MAXM=(1<<17);
vector<pair<int,int> >g[MAXN];
int distu[MAXN],distv[MAXN];
int parEdgeU[MAXN];
int parEdgeV[MAXN];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    for(int i=0;i<M;i++)
    {
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    vector<int>w;
    w=vector<int>(M,0);
    long long dist=(long long)ask(w);
    long long low=0,high=M-1,best;
    while(low<=high)
    {
        int mid=(low+high)/2;
        for(int j=0;j<w.size();j++)w[j]=0;
        for(int j=0;j<=mid;j++)
        {
            w[j]=1;
        }
        if(ask(w)==dist)
        {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=1;j<tv.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j=1;j<tu.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:158:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |     answer(s,t);
      |     ~~~~~~^~~~~
highway.cpp:158:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:39:17: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int u=U[best],v=V[best];
      |                 ^

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