Submission #597140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
597140	2022-07-15T14:45:48 Z	yutabi	Highway Tolls (IOI18_highway)	C++14	6 / 100	120 ms	8488 KB

highway

#include "highway.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;


vector <int> remap_edge;
vector <int> remap_node;



ll my_ask(vector <int> vals)
{
    vector <int> nw_vals(vals.size());

    for(int i=0;i<vals.size();i++)
    {
        nw_vals[remap_edge[i]]=vals[i];
    }

    return ask(nw_vals);
}


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    ll a=A;

    vector <vector <ii> > c(N);

    remap_node=vector <int> (N);
    remap_edge=vector <int> (N);

    for(int i=0;i<U.size();i++)
    {
        c[U[i]].pb(ii(V[i],i));
        c[V[i]].pb(ii(U[i],i));
    }

    int start;

    for(int i=0;i<N;i++)
    {
        if(c[i].size()==1)
        {
            start=i;
        }
    }

    vector <bool> v(N,0);


    int curr=start;

    for(int i=0;i<N;i++)
    {
        v[curr]=1;
        remap_node[i]=curr;

        if(i+1!=N)
        {
            for(int j=0;j<c[curr].size();j++)
            {
                if(v[c[curr][j].first]==0)
                {
                    int nw=c[curr][j].first;
                    int edge=c[curr][j].second;

                    remap_edge[i]=edge;

                    curr=nw;

                    break;
                }
            }
        }
    }

    /*for(int i=0;i<N;i++)
    {
        printf("%d ",remap_node[i]);
    }

    printf("\n");

    for(int i=0;i<N-1;i++)
    {
        printf("%d ",remap_edge[i]);
    }

    printf("\n");*/

    vector <int> query(N-1,0);

    ll low=my_ask(query);
    ll dist=low/a;

    int l=0;
    int r=N-2;
    int m=(l+r)/2;

    while(l!=r)
    {
        for(int i=0;i<=m;i++)
        {
            query[i]=1;
        }

        for(int i=m+1;i<N-1;i++)
        {
            query[i]=0;
        }

        ll res=my_ask(query);

        if(res>low)
        {
            r=m;
        }

        else
        {
            l=m+1;
        }

        m=(l+r)/2;
    }

    //printf("\n%d %d %d %d %d %d\n\n",l,m,r,dist,remap_node[l],remap_node[l+dist]);

    answer(remap_node[l], remap_node[l+dist]);
}

Compilation message

highway.cpp: In function 'll my_ask(std::vector<int>)':
highway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<U.size();i++)
      |                 ~^~~~~~~~~
highway.cpp:70: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]
   70 |             for(int j=0;j<c[curr].size();j++)
      |                         ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	208 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1104 KB	Output is correct
2	Correct	23 ms	2120 KB	Output is correct
3	Correct	39 ms	2952 KB	Output is correct
4	Correct	120 ms	8424 KB	Output is correct
5	Correct	81 ms	8428 KB	Output is correct
6	Correct	82 ms	8488 KB	Output is correct
7	Correct	102 ms	8412 KB	Output is correct
8	Correct	118 ms	8408 KB	Output is correct
9	Correct	117 ms	8416 KB	Output is correct