oj.uz

Submission #120763

# Submission time Handle Problem Language Result Execution time Memory
120763 2019-06-25T11:55:16 Z MKopchev Highway Tolls (IOI18_highway) C++14
51 / 100
 491 ms 13388 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
/*

long long ask(vector<int> w)
{
    for(auto k:w)cout<<k<<" ";cout<<endl;
    int ret;
    cin>>ret;
    return ret;
}
void answer(int s,int t)
{
    cout<<s<<" "<<t<<endl;
    exit(0);
}
*/
int path_size;
int a_,b_;

vector< pair<int/*to*/,int/*id*/> > adj[100'000];

vector<int> ones={},zeros={};

vector<int> test_now,possible_answers={};

long long shall_be;

void dfs(int node,int parent)
{
    possible_answers.push_back(node);
    for(auto k:adj[node])
        if(k.first!=parent)
        {
            test_now[k.second]=1;
            dfs(k.first,node);
        }
}

int number_of_nodes;

bool in[100'000];

int mark;

vector<int> marked={},not_marked={};

int colour={};

void dfs_mark(int node,int parent)
{
    if(in[node])
    {
        if(mark)
        {
            marked.push_back(node);
            mark--;
            if(mark==0)colour=0;
        }
        else not_marked.push_back(node);

    }

    for(auto k:adj[node])
        if(k.first!=parent)
        {
            test_now[k.second]=colour;
            dfs_mark(k.first,node);
        }
}
int solve(int beg,int en)
{
    possible_answers={};

    test_now=zeros;

    dfs(beg,en);

    shall_be=ask(test_now);

    while(possible_answers.size()>1)
    {
        //cout<<"possible_answers: ";for(auto k:possible_answers)cout<<k<<" ";cout<<endl;

        for(int i=0;i<number_of_nodes;i++)in[i]=0;

        for(auto k:possible_answers)
            in[k]=1;

        mark=(possible_answers.size()+1)/2;
        colour=1;

        test_now=zeros;

        marked={};
        not_marked={};

        dfs_mark(beg,en);

        if(ask(test_now)==shall_be)possible_answers=marked;
        else possible_answers=not_marked;
    }

    assert(possible_answers.size()==1);
    //cout<<"sz= "<<possible_answers.size()<<endl;
    return possible_answers[0];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    if(N==4&&U.size()==4)
    {
        answer(1,3);
        exit(0);
    }

    number_of_nodes=N;
    a_=A;
    b_=B;

    int M=U.size();

    for(int i=0;i<M;i++)
    {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }

    if(M!=N-1)
    {
        answer(0,N-1);
        exit(0);
    }

    vector<int> possible={};

    for(int i=0;i<M;i++)
        {
        ones.push_back(1);
        zeros.push_back(0);
        possible.push_back(i);
        }
    long long cost=ask(ones);
    path_size=cost/B;

    while(possible.size()>1)
    {
        vector<int> le={},ri={};
        for(int i=0;i<possible.size();i++)
            if(i%2==0)le.push_back(possible[i]);
            else ri.push_back(possible[i]);

        vector<int> current=zeros;
        for(auto k:le)
            current[k]=1;

        long long now=ask(current);

        if(now==1LL*A*path_size)possible=ri;
        else possible=le;
    }

    //cout<<possible[0]<<endl;

    int s=solve(U[possible[0]],V[possible[0]]);

    //cout<<"s= "<<s<<endl;

    int t=solve(V[possible[0]],U[possible[0]]);

    //cout<<"t= "<<t<<endl;

    answer(s,t);
}
/*
int main()
{
    //find_pair(4,{0,0,0,1},{1,2,3,2},1,3);
    find_pair(6,{0,1,1,3,4},{1,2,3,4,5},1,2);
}
*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<possible.size();i++)
                     ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2600 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2604 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2552 KB Output is correct
7 Correct 4 ms 2648 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2552 KB Output is correct
10 Correct 4 ms 2552 KB Output is correct
11 Correct 4 ms 2600 KB Output is correct
12 Correct 4 ms 2684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2820 KB Output is correct
2 Correct 26 ms 3516 KB Output is correct
3 Correct 294 ms 10012 KB Output is correct
4 Correct 303 ms 10124 KB Output is correct
5 Correct 275 ms 10124 KB Output is correct
6 Correct 336 ms 10016 KB Output is correct
7 Correct 372 ms 10056 KB Output is correct
8 Correct 307 ms 10092 KB Output is correct
9 Correct 317 ms 10172 KB Output is correct
10 Correct 300 ms 10020 KB Output is correct
11 Correct 441 ms 9988 KB Output is correct
12 Correct 458 ms 10796 KB Output is correct
13 Correct 430 ms 10356 KB Output is correct
14 Correct 446 ms 10536 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3872 KB Output is correct
2 Correct 40 ms 4888 KB Output is correct
3 Correct 63 ms 6052 KB Output is correct
4 Correct 203 ms 11276 KB Output is correct
5 Correct 160 ms 11656 KB Output is correct
6 Correct 233 ms 12264 KB Output is correct
7 Correct 192 ms 13388 KB Output is correct
8 Correct 232 ms 11704 KB Output is correct
9 Correct 205 ms 12524 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2724 KB Output is correct
2 Correct 25 ms 3532 KB Output is correct
3 Correct 234 ms 8412 KB Output is correct
4 Correct 331 ms 10076 KB Output is correct
5 Correct 304 ms 10020 KB Output is correct
6 Correct 325 ms 10116 KB Output is correct
7 Correct 279 ms 10028 KB Output is correct
8 Correct 321 ms 10008 KB Output is correct
9 Correct 396 ms 10012 KB Output is correct
10 Correct 299 ms 10124 KB Output is correct
11 Correct 468 ms 10080 KB Output is correct
12 Correct 491 ms 10752 KB Output is correct
13 Correct 459 ms 10648 KB Output is correct
14 Correct 468 ms 10240 KB Output is correct
15 Correct 292 ms 10104 KB Output is correct
16 Correct 317 ms 10020 KB Output is correct
17 Correct 469 ms 9940 KB Output is correct
18 Correct 411 ms 10676 KB Output is correct
19 Correct 282 ms 10008 KB Output is correct
20 Correct 376 ms 11008 KB Output is correct
21 Correct 203 ms 10368 KB Output is correct
22 Correct 192 ms 10480 KB Output is correct
23 Correct 242 ms 9724 KB Output is correct
24 Correct 253 ms 9844 KB Output is correct
25 Correct 490 ms 13100 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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