Submission #283230

#	Time	Username	Problem	Language	Result	Execution time	Memory
283230		stoyan_malinin	Highway Tolls (IOI18_highway)	C++14	90 / 100	324 ms	11960 KiB

highway

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

#include <set>
#include <queue>
#include <vector>
#include <assert.h>
#include <iostream>

using namespace std;

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

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

vector <int> edgeInd;
int getFirstEdge()
{
    vector <int> v;
    v.assign(edgeInd.size(), 0);

    int ind = 0;
    long long base = ask(v);

    int l = 0, r = edgeInd.size() - 1, mid;
    while(l!=r)
    {
        mid = (l+r)/2;
        for(int i = 0;i<edgeInd.size();i++)
        {
            if(edgeInd[i]<=mid) v[i] = 1;
            else v[i] = 0;
        }

        if(ask(v)!=base) r = mid;
        else l = mid + 1;
    }

    return l;
}

int getLastEdge(int addedEdges)
{
    vector <int> v;
    v.assign(edgeInd.size(), 0);

    int ind = 0;
    long long base = ask(v);

    int l = -1, r = addedEdges - 1, mid;
    while(l!=r)
    {
        mid = (l+r+1)/2;
        for(int i = 0;i<edgeInd.size();i++)
        {
            if(edgeInd[i]>=mid) v[i] = 1;
            else v[i] = 0;
        }

        if(ask(v)!=base) l = mid;
        else r = mid - 1;
    }

    return l;
}

vector <int> getDist(int x)
{
    queue <int> q;

    vector <int> dist;
    dist.assign(n, -1);

    q.push(x);
    dist[x] = 0;
    while(q.empty()==false)
    {
        x = q.front();
        q.pop();

        for(pair <int, int> item: graph[x])
        {
            if(dist[item.first]==-1)
            {
                dist[item.first] = dist[x] + 1;
                q.push(item.first);
            }
        }
    }

    return dist;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    //cout << '\n';

    n = N;
    for(int i = 0;i<U.size();i++)
    {
        graph[ U[i] ].push_back({V[i], i});
        graph[ V[i] ].push_back({U[i], i});
    }
    for(int i = 0;i<U.size();i++)
    {
        edgeInd.push_back(i);
    }


    int e = getFirstEdge();
    int nodes[] = {U[e], V[e]};
    //cout << nodes[0] << " " << nodes[1] << '\n';

    vector <int> dist[2];
    dist[0] = getDist(nodes[0]);
    dist[1] = getDist(nodes[1]);

    int ans[2];
    for(int rep = 0;rep<2;rep++)
    {
        //cout << " ----- " << rep << " ------ " << '\n';

        int addedEdges = 0;
        for(int i = 0;i<edgeInd.size();i++) edgeInd[i] = -1;

        queue <int> q;
        vector <int> d(n, -1);
        vector <int> vertexOfEdge(U.size(), -1);

        q.push(nodes[rep]);
        d[ nodes[rep] ] = 0;
        while(q.empty()==false)
        {
            int x = q.front();
            q.pop();

            //cout << x << " -> " << d[x] << '\n';
            for(pair <int, int> item: graph[x])
            {
                if(dist[rep][item.first]<dist[rep^1][item.first])
                {
                    if(d[item.first]==-1)
                    {
                        d[item.first] = d[x] + 1;
                        q.push(item.first);

                        edgeInd[item.second] = addedEdges;
                        vertexOfEdge[addedEdges] = item.first;

                        //cout << item.second << ": " << addedEdges << '\n';

                        addedEdges++;
                    }
                    else if(d[item.first]==d[x]+1)
                    {
                        edgeInd[item.second] = U.size() + 1;
                    }
                }
                else if(item.second!=e)
                {
                    edgeInd[item.second] = U.size() + 1;
                }
            }
        }

        int lastE = getLastEdge(addedEdges);

        //cout << lastE << '\n';
        ans[rep] = ((lastE==-1)?nodes[rep]:vertexOfEdge[lastE]);
    }

    //cout << ans[0] << " -- " << ans[1] << '\n';
    answer(ans[0], ans[1]);

}

/*
4 4
1 3
3 2

0 1
0 2
0 3
1 2
*/

Compilation message (stderr)

highway.cpp: In function 'int getFirstEdge()':
highway.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i = 0;i<edgeInd.size();i++)
      |                       ~^~~~~~~~~~~~~~~
highway.cpp:24:9: warning: unused variable 'ind' [-Wunused-variable]
   24 |     int ind = 0;
      |         ^~~
highway.cpp: In function 'int getLastEdge(int)':
highway.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i = 0;i<edgeInd.size();i++)
      |                       ~^~~~~~~~~~~~~~~
highway.cpp:49:9: warning: unused variable 'ind' [-Wunused-variable]
   49 |     int ind = 0;
      |         ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 0;i<U.size();i++)
      |                   ~^~~~~~~~~
highway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0;i<U.size();i++)
      |                   ~^~~~~~~~~
highway.cpp:126:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i = 0;i<edgeInd.size();i++) edgeInd[i] = -1;
      |                       ~^~~~~~~~~~~~~~~

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