oj.uz

Submission #75081

# Submission time Handle Problem Language Result Execution time Memory
75081 2018-09-08T09:05:25 Z faustaadp Highway Tolls (IOI18_highway) C++17
0 / 100
 442 ms 262148 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,jar,L,R,C,bew[101010];
vector<ll> v[101010],mun;
void dfs(ll aa,ll bb,ll cc)
{
    if(bb==jar)
        mun.pb(aa);
    ll ii;
    for(ii=0;ii<v[aa].size();ii++)
        if(v[aa][ii]!=cc)
        {
            bew[v[aa][ii]]=aa;
            dfs(v[aa][ii],bb+1,aa);
        }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    ll M = U.size();
    for(i=0;i<M;i++)
    {
        v[U[i]].pb(V[i]);
        v[V[i]].pb(U[i]);
    }
    vector<int> tan(M);
    for(i=0;i<M;i++)
        tan[i]=0;
    jar=ask(tan)/A;
    dfs(0,0,0);
    //cout<<jar*A<<"\n";
 //   for(i=0;i<mun.size();i++)cout<<mun[i]<<" ";cout<<"\n";
    L=0;
    R=mun.size()-1;
    while(L<R)
    {
        C=(L+R)/2;
        for(i=0;i<M;i++)
            tan[i]=0;
        for(i=L;i<=C;i++)
            tan[bew[mun[i]]]=1;
        //for(i=0;i<M;i++)cout<<tan[i]<<" ";cout<<"\n";
        //cout<<L<<" "<<R<<" "<<ask(tan)<<"\n";
        if(ask(tan)>A*jar)R=C;
        else    L=C+1;
    }
    answer(0, mun[L]);
}

Compilation message

highway.cpp: In function 'void dfs(long long int, long long int, long long int)':
highway.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ii=0;ii<v[aa].size();ii++)
              ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 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 5 ms 2680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 442 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 415 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -