Submission #283072

#	Time	Username	Problem	Language	Result	Execution time	Memory
283072		stoyan_malinin	Highway Tolls (IOI18_highway)	C++14	51 / 100	246 ms	262148 KiB

highway

#include "highway.h"
//#include "grader.cpp"

#include <set>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXLog = 18;

int n;
vector <int> graph[MAXN];
vector <pair <int, int>> edges;

bool inVector[MAXN];
long long askVector(vector <int> nodes)
{
    for(int x: nodes) inVector[x] = true;

    vector <int> v(edges.size());
    for(int i = 0;i<edges.size();i++)
    {
        if(inVector[ edges[i].first ]==true && inVector[ edges[i].second ]==true) v[i] = 1;
        else v[i] = 0;
    }

    //cout << " -> " << v.size() << '\n';
    for(int x: nodes) inVector[x] = false;
    return ask(v);
}

int parent[MAXN], depth[MAXN];
void DFSInit(int x, int last, int level)
{
    parent[x] = last;
    depth[x] = level;

    for(int i = 0;i<graph[x].size();i++)
    {
        if(graph[x][i]==last)
        {
            graph[x].erase(graph[x].begin()+i);
            break;
        }
    }

    for(int y: graph[x])
    {
        DFSInit(y, x, level+1);
    }
}

vector <int> bfsOrder;
void BFSInit(int x)
{
    queue <int> q;
    q.push(x);

    while(q.empty()==false)
    {
        x = q.front();q.pop();
        bfsOrder.push_back(x);

        for(int y: graph[x])
        {
            q.push(y);
        }
    }
}

vector <int> getVector(vector <int> &v, int l, int r)
{
    vector <int> out;
    for(int i = l;i<=r;i++) out.push_back(v[i]);

    return out;
}

pair <int, int> findLCA(long long A, long long B, long long pathLen)
{
    int ind = 0;
    for(int step = MAXLog;step>=0;step--)
    {
        if(ind+(1<<step)>=bfsOrder.size()) continue;
        if(askVector(getVector(bfsOrder, 0, ind+(1<<step)))==pathLen*A) ind += (1<<step);
    }

    ind++;
    return {bfsOrder[ind], parent[ bfsOrder[ind] ]};
}

void DFSMark(int x, int last, int excluded, vector <int> &v)
{
    v.push_back(x);
    for(int y: graph[x])
    {
        if(y==excluded) continue;
        DFSMark(y, x, excluded, v);
    }
}

int useTree(int root, int excluded, long long A, long long B, long long pathLen)
{
    vector <int> v;
    DFSMark(root,-1, excluded, v);
    if(v.size()==1) return v[0];

    //for(int x: v) cout << x << " ";
    //cout << '\n';

    long long base = askVector(v);
    if(base==pathLen*A) return root;

    int ind = 0;
    for(int step = MAXLog;step>=0;step--)
    {
        if(ind+(1<<step)>=v.size()) continue;
        if(askVector(getVector(v, 0, ind+(1<<step)))!=base) ind += (1<<step);
    }

    return v[ind+1];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    for(int i = 0;i<U.size();i++)
    {
        graph[ U[i] ].push_back(V[i]);
        graph[ V[i] ].push_back(U[i]);
        edges.push_back({U[i], V[i]});
    }

    DFSInit(0, -1, 0);
    BFSInit(0);

    int pathLen = askVector({})/A;
    pair <int, int> lcaPair = findLCA(A, B, pathLen);

    int lca = lcaPair.second;
    int rootS = lcaPair.first;

    int S = useTree(rootS, -1, A, B, pathLen);

    //cout << lca << " -- " << rootS << '\n';
    //cout << S << '\n';

    int T = -1;
    if(depth[lca]-depth[S]==pathLen) T = lca;
    else T = useTree(lca, rootS, A, B, pathLen);

    //cout << T << '\n';

    answer(S, T);
}

/*
6 5
1 2
1 5

0 1
0 2
1 3
1 4
2 5
*/

Compilation message (stderr)

highway.cpp: In function 'long long int askVector(std::vector<int>)':
highway.cpp:24: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]
   24 |     for(int i = 0;i<edges.size();i++)
      |                   ~^~~~~~~~~~~~~
highway.cpp: In function 'void DFSInit(int, int, int)':
highway.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0;i<graph[x].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
highway.cpp: In function 'std::pair<int, int> findLCA(long long int, long long int, long long int)':
highway.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         if(ind+(1<<step)>=bfsOrder.size()) continue;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'int useTree(int, int, long long int, long long int, long long int)':
highway.cpp:120:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if(ind+(1<<step)>=v.size()) continue;
      |            ~~~~~~~~~~~~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i = 0;i<U.size();i++)
      |                   ~^~~~~~~~~

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