제출 #523756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523756		InternetPerson10	통행료 (IOI18_highway)	C++17	51 / 100	200 ms	20556 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<int, int> rootedTree(int N, vector<int> U, vector<int> V, int A, int B, ll dep = 0, int root = 0) { // tree, one is determined (by default 0)
    int M = U.size();
    vector<int> v(M, 1);
    if(dep == 0) dep = ask(v) / B;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    queue<pair<int, pair<int, int>>> q;
    vector<pair<int, int>> candidates;
    vector<bool> taken(N, false);
    q.push({0, {root, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        // cout << p.first << ' ' << p.second.first << '\n';
        taken[p.second.first] = true;
        if(p.first == dep) {
            candidates.push_back(p.second); 
            continue;
        }
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    int g = 1;
    while((1 << g) < candidates.size()) g++;
    ll ans = 0;
    for(int i = 0; i < g; i++) {
        for(int j = 0; j < candidates.size(); j++) {
            if(j & (1 << i)) v[candidates[j].second] = 0;
        }
        if(ask(v) != dep * B) ans += (1 << i);
        for(int j = 0; j < candidates.size(); j++) {
            v[candidates[j].second] = 1;
        }
    }
    // cout << candidates.size() << " candidates\n";
    return {root, candidates[ans].first};
}

pair<int, int> generalTree(int N, vector<int> U, vector<int> V, int A, int B) { // tree
    int M = U.size();
    vector<int> v(M, 1);
    vector<vector<pair<int, int>>> adj(N);
    vector<vector<pair<int, int>>> depths(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vector<bool> taken(N, false);
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {0, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        taken[p.second.first] = true;
        depths[p.first].push_back(p.second);
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    while(depths.back().size() == 0) depths.pop_back();
    ll largeLength = ask(v);
    int l = 1, r = depths.size();
    while(l != r - 1) {
        int mid = (l + r) / 2;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 0;
            }
        }
        if(ask(v) == largeLength) r = mid;
        else l = mid;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 1;
            }
        }
    }
    int g = 0;
    while((1 << g) < depths[l].size()) g++;
    int ans = 0;
    for(int i = 0; i < g; i++) { // Funny way to divide people into two groups, check for good
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 0;
        }
        if(ask(v) != largeLength) ans += (1 << i);
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 1;
        }
    }
    // cout << "Determined one of them to be " << depths[l][ans].first << '\n';
    return rootedTree(N, U, V, A, B, 0, depths[l][ans].first);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    pair<int, int> ans;
    if(U.size() + 1 == N) ans = generalTree(N, U, V, A, B);    
    else {

    }
    answer(ans.first, ans.second);
}

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

highway.cpp: In function 'std::pair<int, int> rootedTree(int, std::vector<int>, std::vector<int>, int, int, ll, int)':
highway.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while((1 << g) < candidates.size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
highway.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> generalTree(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:77:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     while((1 << g) < depths[l].size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~
highway.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:110:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     if(U.size() + 1 == N) ans = generalTree(N, U, V, A, B);
      |        ~~~~~~~~~~~~~^~~~

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