Submission #971976

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
971976	2024-04-29 16:03:38	onlk97	Highway Tolls (IOI18_highway)	C++14	51 / 100	238 ms	262144 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;
vector <pair <int,int> > g[100010];
int pa[100010],dep[100010];
vector <int> is;
void dfs(int cur,int prv,bool r){
    if (r) dep[cur]=0;
    else dep[cur]=dep[prv]+1;
    for (auto i:g[cur]){
        if (i.first!=prv){
            pa[i.first]=i.second;
            is.push_back(i.second);
            dfs(i.first,cur,0);
        }
    }
}
void find_pair(int n,vector <int> u,vector <int> v,int a,int b){
    int m=u.size();
    vector <int> tt(m,0);
    long long dist0=ask(tt);
    int l=0,r=m-1;
    while (l<r){
        int mid=(l+r)/2;
        vector <int> tp(m,0);
        for (int i=l; i<=mid; i++) tp[i]=1;
        long long dist1=ask(tp);
        if (dist0!=dist1) r=mid;
        else l=mid+1;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
      |                       ~^~~~~~~~~~~~~~~~~~
highway.cpp:52:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]);
      |                           ~^~~~~~~~~~~~~~~~~~
highway.cpp:54:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
      |                                           ~^~~~~~~~~~~~
highway.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
      |                       ~^~~~~~~~~~~~~~~~~~
highway.cpp:76:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]);
      |                           ~^~~~~~~~~~~~~~~~~~
highway.cpp:78:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
      |                                           ~^~~~~~~~~~~~

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