oj.uz

Submission #342063

# Submission time Handle Problem Language Result Execution time Memory
342063 2021-01-01T09:18:19 Z inwbear Highway Tolls (IOI18_highway) C++14
51 / 100
 186 ms 16620 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
vector<int>v[90005];
vector<int>hi[90005];
int h[90005];

void dfs(int nn,int hn)
{
    h[nn]=hn;
    for(int i=0;i<v[nn].size();i++)
    {
        if(h[v[nn][i]]==0)
        {
            dfs(v[nn][i],hn+1);
        }
    }
    return;
}

void find_pair(int n,vector<int>a,vector<int>b,int c1,int c2)
{
    int m=a.size(),re1,re2,st=1,ed=90000,mid,hh=90000;
    LL dis,tp;
    vector<int>co(m);
    for(int i=0;i<m;i++)
    {
        v[a[i]].pb(b[i]);
        v[b[i]].pb(a[i]);
    }
    dfs(0,1);
    for(int i=0;i<m;i++)
    {
        hi[max(h[a[i]],h[b[i]])].pb(i);
    }
    for(int i=0;i<m;i++)co[i]=0;
    dis=ask(co);
    while(st<=ed)
    {
        mid=(st+ed)/2;
        for(int i=0;i<m;i++)co[i]=0;
        for(int i=mid+1;i<=90000;i++)
        {
            for(int j=0;j<hi[i].size();j++)
            {
                co[hi[i][j]]=1;
            }
        }
        tp=ask(co);
        if(tp==dis)
        {
            hh=min(hh,mid);
            ed=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    st=0,ed=hi[hh].size()-1,re1=hi[hh].size()-1;
    while(st<=ed)
    {
        mid=(st+ed)/2;
        for(int i=0;i<m;i++)co[i]=0;
        for(int i=st;i<=mid;i++)
        {
            co[hi[hh][i]]=1;
        }
        tp=ask(co);
        if(tp==dis)
        {
            st=mid+1;
        }
        else
        {
            re1=min(re1,mid);
            ed=mid-1;
        }
    }
    re1=hi[hh][re1];
    if(h[a[re1]]>h[b[re1]])re1=a[re1];
    else re1=b[re1];
    for(int i=0;i<90005;i++)h[i]=0;
    dfs(re1,1);
    for(int i=0;i<90005;i++)hi[i].clear();
    hh=(dis/c1)+1;
    for(int i=0;i<m;i++)
    {
        hi[max(h[a[i]],h[b[i]])].pb(i);
        //printf("%d %d %d\n",i,h[a[i]],h[b[i]]);
    }
    st=0,ed=hi[hh].size()-1,re2=hi[hh].size()-1;
    while(st<=ed)
    {
        mid=(st+ed)/2;
        for(int i=0;i<m;i++)co[i]=0;
        for(int i=st;i<=mid;i++)
        {
            co[hi[hh][i]]=1;
        }
        tp=ask(co);
        if(tp==dis)
        {
            st=mid+1;
        }
        else
        {
            re2=min(re2,mid);
            ed=mid-1;
        }
    }
    re2=hi[hh][re2];
    if(h[a[re2]]>h[b[re2]])re2=a[re2];
    else re2=b[re2];
    //printf("%d %d",re1,re2);
    answer(re1,re2);
    return;
}

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<v[nn].size();i++)
      |                 ~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int j=0;j<hi[i].size();j++)
      |                         ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4864 KB Output is correct
2 Correct 6 ms 4844 KB Output is correct
3 Correct 6 ms 4844 KB Output is correct
4 Correct 6 ms 4876 KB Output is correct
5 Correct 6 ms 4844 KB Output is correct
6 Correct 7 ms 4844 KB Output is correct
7 Correct 6 ms 4844 KB Output is correct
8 Correct 6 ms 4844 KB Output is correct
9 Correct 6 ms 4844 KB Output is correct
10 Correct 6 ms 4844 KB Output is correct
11 Correct 6 ms 4844 KB Output is correct
12 Correct 6 ms 4844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4972 KB Output is correct
2 Correct 21 ms 5484 KB Output is correct
3 Correct 145 ms 10364 KB Output is correct
4 Correct 159 ms 10384 KB Output is correct
5 Correct 155 ms 10364 KB Output is correct
6 Correct 138 ms 10220 KB Output is correct
7 Correct 145 ms 10308 KB Output is correct
8 Correct 154 ms 10644 KB Output is correct
9 Correct 154 ms 10496 KB Output is correct
10 Correct 158 ms 10240 KB Output is correct
11 Correct 182 ms 11740 KB Output is correct
12 Correct 181 ms 12540 KB Output is correct
13 Correct 178 ms 11644 KB Output is correct
14 Correct 164 ms 12012 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6124 KB Output is correct
2 Correct 33 ms 7524 KB Output is correct
3 Correct 42 ms 8812 KB Output is correct
4 Correct 124 ms 16580 KB Output is correct
5 Correct 126 ms 16584 KB Output is correct
6 Correct 118 ms 16620 KB Output is correct
7 Correct 120 ms 16492 KB Output is correct
8 Correct 118 ms 16576 KB Output is correct
9 Correct 113 ms 16592 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 19 ms 5484 KB Output is correct
3 Correct 114 ms 9104 KB Output is correct
4 Correct 152 ms 10236 KB Output is correct
5 Correct 145 ms 10220 KB Output is correct
6 Correct 161 ms 10368 KB Output is correct
7 Correct 141 ms 10276 KB Output is correct
8 Correct 152 ms 10208 KB Output is correct
9 Correct 157 ms 10252 KB Output is correct
10 Correct 156 ms 10268 KB Output is correct
11 Correct 164 ms 11528 KB Output is correct
12 Correct 174 ms 12424 KB Output is correct
13 Correct 164 ms 11880 KB Output is correct
14 Correct 172 ms 12256 KB Output is correct
15 Correct 142 ms 10224 KB Output is correct
16 Correct 145 ms 10612 KB Output is correct
17 Correct 175 ms 12096 KB Output is correct
18 Correct 186 ms 12088 KB Output is correct
19 Correct 144 ms 10248 KB Output is correct
20 Correct 174 ms 12788 KB Output is correct
21 Correct 135 ms 10724 KB Output is correct
22 Correct 132 ms 10596 KB Output is correct
23 Correct 137 ms 10596 KB Output is correct
24 Correct 144 ms 11168 KB Output is correct
25 Correct 177 ms 15932 KB Output is correct

Subtask #5
0 / 18.0

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