제출 #361674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361674		cuongdh1912	통행료 (IOI18_highway)	C++14	18 / 100	3101 ms	13584 KiB

highway

#include "highway.h"
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define PAIR(i,j) pair<i, j>

vector<vector<pair<int, int> > > graph;
vector<vector<int> > spreadTree;
vector<int> last;
void addLayer2SpreadTree(int value, int i) {
    spreadTree[i].push_back(value);
//    for auto i: l {
//
//    }
}
std::vector<int> UU;
std::vector<int> VV;
int MM;
long long total0;

void doSpread(int from, long long maxStep) {
    spreadTree.clear();
    last.clear();
    last.resize(MM);
    bool visisted[MM];
    fill(visisted, visisted + MM, false);
    
    // spread from 0
    queue<pair<int, int> > q;
    q.push(make_pair(from, 0));
    visisted[from] = true;
    last[from] = UU[from];
    while (!q.empty()) {
        pair<int, int> v = q.front();
        q.pop();
        
        if (v.second > maxStep) {
            break;
        }
        if (v.second >= spreadTree.size()) {
            spreadTree.push_back(vector<int>());
        }
        spreadTree[v.second].push_back(v.first);
        vector<pair<int, int> > join = graph[UU[v.first]];
        join.insert(join.end(), graph[VV[v.first]].begin(), graph[VV[v.first]].end());
        for (auto e : join) {
            if (!visisted[e.second]) {
                visisted[e.second] = true;
                last[e.second] = e.first;
                q.push(make_pair(e.second, v.second + 1));
            }
        }
    }
}
int binarySearch() {
    int left = 0, right = spreadTree.size() - 1;
    std::vector<int> w(MM);
    fill(w.begin(), w.end(), 0);
    while (left < right) {
        int mid = left + (right - left) / 2;
        int k = 0;
        for (int i = left; i <= right; ++i) {
            if (i > mid) {
                k = 1;
            }
            for (auto j: spreadTree[i]) {
                w[j] = k;
            }
        }
        
        long long toll = ask(w);
        if (total0 != toll) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    fill(w.begin(), w.end(), 0);
    int step = left;
    left = 0; right = spreadTree[step].size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        int k = 0;
        for (int i = left; i <= right; ++i) {
            if (i > mid) {
                k = 1;
            }
            w[spreadTree[step][i]] = k;
        }
        
        long long toll = ask(w);
        if (total0 != toll) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return spreadTree[step][left];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    UU = U; VV = V;
    MM = M;
    graph.resize(N);
    for (int i = 0; i < M; ++i) {
        graph[U[i]].push_back(make_pair(V[i], i));
        graph[V[i]].push_back(make_pair(U[i], i));
    }
    
    std::vector<int> w(MM);
    for (int i = 0; i < MM; ++i) {
        w[i] = 0;
    }
    total0 = ask(w);
    
    
    // spread from 0
    doSpread(0, M);
    int s, t;
    long long maxStep = total0 / A;
    // binary search
    int midEdge = binarySearch();
    // spread to max
    doSpread(midEdge, maxStep);
    int lastPoint = binarySearch();
    s = last[lastPoint];
    doSpread(lastPoint, maxStep);
    int secondPoint = binarySearch();
    t = last[secondPoint];
    
    answer(s, t);
}

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

highway.cpp: In function 'void doSpread(int, long long int)':
highway.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (v.second >= spreadTree.size()) {
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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