제출 #523769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523769		InternetPerson10	통행료 (IOI18_highway)	C++17	51 / 100	211 ms	25972 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, 0);
    if(dep == 0) dep = ask(v) / A;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) {
            v[i] = 1;
            continue;
        }
        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] = 1;
        }
        if(ask(v) != dep * A) ans += (1 << i);
        for(int j = 0; j < candidates.size(); j++) {
            v[candidates[j].second] = 0;
        }
    }
    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, 0);
    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) {
            v[i] = 1;
            continue;
        }
        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] = 1;
            }
        }
        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] = 0;
            }
        }
    }
    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] = 1;
        }
        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] = 0;
        }
    }
    // 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 {
        int M = U.size();
        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});
        }
        vector<bool> taken(N, false);
        vector<int> depths(N);
        queue<pair<int, pair<int, int>>> q;
        q.push({0, {0, -1}});
        depths[0] = 0;
        while(q.size()) {
            auto p = q.front(); q.pop();
            taken[p.second.first] = true;
            for(auto g : adj[p.second.first]) {
                if(taken[g.first]) {
                    if(depths[g.first] > depths[p.second.first]) {
                        U[p.second.second] = V[p.second.second] = -1;
                    }
                    continue;
                }
                q.push({p.first + 1, g});
                depths[g.first] = p.first + 1;
            }
        }
        ans = generalTree(N, U, V, A, B);
    }
    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:38: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]
   38 |     while((1 << g) < candidates.size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
highway.cpp:41: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]
   41 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp:45: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]
   45 |         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:82: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]
   82 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:89: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]
   89 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:96: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]
   96 |     while((1 << g) < depths[l].size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~
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:104: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]
  104 |         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:115:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |     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