제출 #587484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587484		definitelynotmee	통행료 (IOI18_highway)	C++17	18 / 100	167 ms	14160 KiB

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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31