Submission #587484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587484	2022-07-02T00:59:45 Z	definitelynotmee	Highway Tolls (IOI18_highway)	C++17	18 / 100	167 ms	14160 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e9;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    ll base = ask(vector<int>(M));
    ll dist = base/A;

    vector<int> pai(N);
    matrix<int> g(N),eid(N);
    bool flag = 1;
    for(int i = 0; i < M; i++){
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
        eid[U[i]].push_back(i);
        eid[V[i]].push_back(i);
        flag&=U[i] == i && V[i] == i+1;
    }
    vector<int> s;
    vector<int> qry(M);
    int root = 0;
    auto dfs =[&](int id, int dist, auto dfs)->void{
        if(dist == 0){
            s.push_back(id);
            return;
        }
        for(int i = 0; i < g[id].size(); i++){
            if(eid[id][i] != pai[id]){
                pai[g[id][i]] = eid[id][i];
                dfs(g[id][i],dist-1,dfs);
            }
        }
    };

    if(flag){
        int ini = 0, fim = N-2;
        while(ini!=fim){
            int m = (ini+fim)>>1;
            for(int i = 0; i <= m; i++)
                qry[i] = 1;
            if(ask(qry) > base){
                fim = m;
            } else ini = m+1;
            fill(all(qry),0);
        }
        root = ini;
    }
    
    

    dfs(root,dist,dfs);

    while(s.size()> 1){
        vector<int> l, r;
        for(int i = 0; i < s.size(); i++){
            if(i&1)
                r.push_back(s[i]);
            else l.push_back(s[i]);
        }
        for(int i : l)
            qry[pai[i]] = 1;
        ll ret = ask(qry);
        if(ret > base)
            swap(s,l);
        else swap(s,r);
        fill(all(qry),0);
    }

    answer(root,s[0]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < s.size(); i++){
      |                        ~~^~~~~~~~~~
highway.cpp: In instantiation of 'find_pair(int, std::vector<int>, std::vector<int>, int, int)::<lambda(int, int, auto:23)> [with auto:23 = find_pair(int, std::vector<int>, std::vector<int>, int, int)::<lambda(int, int, auto:23)>]':
highway.cpp:61:22:   required from here
highway.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i = 0; i < g[id].size(); i++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	14 ms	1616 KB	Output is correct
3	Correct	112 ms	12604 KB	Output is correct
4	Correct	119 ms	12600 KB	Output is correct
5	Correct	115 ms	12612 KB	Output is correct
6	Correct	163 ms	12524 KB	Output is correct
7	Correct	110 ms	12520 KB	Output is correct
8	Correct	146 ms	12624 KB	Output is correct
9	Correct	145 ms	12500 KB	Output is correct
10	Correct	117 ms	12600 KB	Output is correct
11	Correct	115 ms	12392 KB	Output is correct
12	Correct	126 ms	12540 KB	Output is correct
13	Correct	120 ms	12540 KB	Output is correct
14	Correct	167 ms	12664 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1524 KB	Output is correct
2	Correct	20 ms	2968 KB	Output is correct
3	Correct	30 ms	4228 KB	Output is correct
4	Correct	131 ms	12728 KB	Output is correct
5	Correct	98 ms	12276 KB	Output is correct
6	Correct	77 ms	14160 KB	Output is correct
7	Correct	94 ms	12280 KB	Output is correct
8	Correct	95 ms	13224 KB	Output is correct
9	Correct	85 ms	12276 KB	Output is correct