oj.uz

Submission #75082

# Submission time Handle Problem Language Result Execution time Memory
75082 2018-09-08T09:07:28 Z faustaadp Highway Tolls (IOI18_highway) C++17
12 / 100
 457 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,xo[101010];
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]]=xo[aa][ii];
            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]);
        xo[U[i]].pb(i);
        xo[V[i]].pb(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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5160 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5060 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5072 KB Output is correct
7 Correct 6 ms 4964 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5080 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 29 ms 6064 KB Output is correct
3 Correct 218 ms 14508 KB Output is correct
4 Correct 215 ms 14484 KB Output is correct
5 Correct 215 ms 14396 KB Output is correct
6 Correct 225 ms 14352 KB Output is correct
7 Correct 266 ms 14424 KB Output is correct
8 Correct 234 ms 14520 KB Output is correct
9 Correct 262 ms 14356 KB Output is correct
10 Correct 222 ms 14480 KB Output is correct
11 Correct 232 ms 14280 KB Output is correct
12 Correct 212 ms 14596 KB Output is correct
13 Correct 247 ms 14224 KB Output is correct
14 Correct 217 ms 13900 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6400 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 7 ms 5252 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 457 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 411 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -