oj.uz

Submission #720423

# Submission time Handle Problem Language Result Execution time Memory
720423 2023-04-08T08:28:13 Z bin9638 Highway Tolls (IOI18_highway) C++17
100 / 100
 294 ms 33424 KB 
#include <bits/stdc++.h>

#ifndef SKY
#include "highway.h"
#endif // SKY

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int times,ktr[N],root[2],cha[N][21],n,m,depth[N],par_id[N];
ll A,B;
ii canh[N],cnt[N];
vector<ii>g[N],ke[N];
queue<int>dq;

#ifdef SKY
int S_ans,T_ans;

void answer(int s,int t)
{
    cout<<s<<" "<<t<<endl;
}

ll dis[55][55];

ll ask(vector<int>w)
{
    memset(dis,0x3f3f,sizeof(dis));
    for(int i=0;i<m;i++)
        dis[canh[i].fs][canh[i].sc]=dis[canh[i].sc][canh[i].fs]=(w[i]==0 ? A : B);
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    return dis[S_ans][T_ans];
}
#endif // SKY

int query;
ll my_ask(vector<int>w)
{
  //  assert(w.size()==m);
    //assert(++query<=50);
    return ask(w);
}

void DFS(int u,int p)
{
    cnt[u].fs=++times;
    for(auto v:g[u])
        if(v.fs!=p)
        {
            par_id[v.fs]=v.sc;
            depth[v.fs]=depth[u]+1;
            cha[v.fs][0]=u;
            DFS(v.fs,u);
        }
    cnt[u].sc=times;
}

bool tren(int u,int v)
{
    return (cnt[u].fs<=cnt[v].fs&&cnt[u].sc>=cnt[v].sc);
}

bool SS(const int&u,const int&v)
{
    return depth[u]<depth[v];
}

int solve(int id,ll val,int cs)
{
    vector<int>s;
    for(int i=0;i<n;i++)
        if(i!=root[0]&&i!=root[1]&&tren(root[id],i))
            s.pb(i);
    sort(s.begin(),s.end(),SS);
   // cout<<id<<endl;
    //for(auto u:s)cout<<u<<" ";cout<<endl;
    int res=root[id],l=-1,r=s.size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        vector<int>hoi(m,1);
        hoi[cs]=0;
        for(int i=0;i<n;i++)
            if(i!=root[0]&&i!=root[1]&&!tren(root[id],i))
                hoi[par_id[i]]=0;
        for(int i=0;i<=mid;i++)
            hoi[par_id[s[i]]]=0;
       // cout<<my_ask(hoi)<<endl;
        if(my_ask(hoi)==val)
        {
            res=(mid==-1 ? root[id] : s[mid]);
            r=mid-1;
        }else
            l=mid+1;
    }
    return res;
}

void find_pair(int cc, vector<int> canh_fs, vector<int> canh_sc, int AAA, int BBB)
{
    n=cc;
    m=canh_fs.size();
    A=AAA;
    B=BBB;
    for(int i=0;i<m;i++)
    {
        canh[i]={canh_fs[i],canh_sc[i]};
        ke[canh[i].fs].pb({canh[i].sc,i});
        ke[canh[i].sc].pb({canh[i].fs,i});
    }
    ll val=my_ask(vector<int>(m,0));
    vector<int>s;
    for(int i=0;i<m;i++)
        s.pb(i);
    while(s.size()>1)
    {
        vector<int>L,R;
        for(int i=0;i<s.size();i++)
            if(i*2<s.size())
                L.pb(s[i]);
                    else R.pb(s[i]);
        vector<int>hoi(m,0);
        for(int i=0;i<=L.back();i++)
            hoi[i]=1;
        if(my_ask(hoi)!=val)
                s=L;
                    else s=R;
    }
    //cout<<canh[s[0]].fs<<" "<<canh[s[0]].sc<<endl;
    root[0]=canh[s[0]].fs;
    root[1]=canh[s[0]].sc;
  //  cout<<root[0]<<" "<<root[1]<<endl;
    queue<int>dq;
    ktr[root[0]]=ktr[root[1]]=1;
    dq.push(root[0]);
    dq.push(root[1]);
    while(!dq.empty())
    {
        int u=dq.front();
        dq.pop();
        for(auto v:ke[u])
            if(ktr[v.fs]==0)
            {
                ktr[v.fs]=1;
                dq.push(v.fs);
                g[u].pb(v);
               // cout<<u<<" "<<v.fs<<endl;
            }
    }
    DFS(root[0],-1);
    DFS(root[1],-1);
    answer(solve(0,val,s[0]),solve(1,val,s[0]));
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    srand(time(0));
    int n,m,A,B;
    map<int,int>mp[110];
    cin>>n>>m>>S_ans>>T_ans>>A>>B;
    vector<int>u(m),v(m);
    for(int i=0;i<m;i++)
        cin>>u[i]>>v[i];
  /* for(int i=0;i<n-1;i++)
    {
        u[i]=i+1;
        v[i]=rand()%(i+1);
         mp[min(u[i],v[i])][max(u[i],v[i])]++;
    }
    for(int i=n-1;i<m;i++)
    {
        u[i]=rand()%n;
        do{
            v[i]=rand()%n;
        }while(u[i]==v[i]||mp[min(u[i],v[i])][max(u[i],v[i])]!=0);
        assert(u[i]!=v[i]);
        mp[min(u[i],v[i])][max(u[i],v[i])]++;
    }*/
  //  for(int i=0;i<m;i++)cout<<u[i]<<" "<<v[i]<<endl;
    find_pair(n,u,v,A,B);
    return 0;
}
#endif

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i=0;i<s.size();i++)
      |                     ~^~~~~~~~~
highway.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             if(i*2<s.size())
      |                ~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 6 ms 9748 KB Output is correct
3 Correct 6 ms 9732 KB Output is correct
4 Correct 5 ms 9680 KB Output is correct
5 Correct 5 ms 9700 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 5 ms 9728 KB Output is correct
8 Correct 6 ms 9680 KB Output is correct
9 Correct 6 ms 9680 KB Output is correct
10 Correct 5 ms 9680 KB Output is correct
11 Correct 5 ms 9680 KB Output is correct
12 Correct 6 ms 9680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9936 KB Output is correct
2 Correct 19 ms 11728 KB Output is correct
3 Correct 177 ms 27476 KB Output is correct
4 Correct 155 ms 27476 KB Output is correct
5 Correct 160 ms 27472 KB Output is correct
6 Correct 159 ms 27484 KB Output is correct
7 Correct 164 ms 27484 KB Output is correct
8 Correct 134 ms 27500 KB Output is correct
9 Correct 155 ms 27484 KB Output is correct
10 Correct 182 ms 27496 KB Output is correct
11 Correct 210 ms 29416 KB Output is correct
12 Correct 197 ms 29812 KB Output is correct
13 Correct 175 ms 29544 KB Output is correct
14 Correct 188 ms 29656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12452 KB Output is correct
2 Correct 29 ms 14840 KB Output is correct
3 Correct 36 ms 17476 KB Output is correct
4 Correct 121 ms 31676 KB Output is correct
5 Correct 135 ms 31776 KB Output is correct
6 Correct 123 ms 32480 KB Output is correct
7 Correct 129 ms 33424 KB Output is correct
8 Correct 132 ms 32172 KB Output is correct
9 Correct 139 ms 32152 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9936 KB Output is correct
2 Correct 28 ms 11704 KB Output is correct
3 Correct 110 ms 23568 KB Output is correct
4 Correct 134 ms 27488 KB Output is correct
5 Correct 165 ms 27484 KB Output is correct
6 Correct 161 ms 27500 KB Output is correct
7 Correct 168 ms 27536 KB Output is correct
8 Correct 139 ms 27468 KB Output is correct
9 Correct 157 ms 27480 KB Output is correct
10 Correct 151 ms 27464 KB Output is correct
11 Correct 180 ms 29204 KB Output is correct
12 Correct 183 ms 29888 KB Output is correct
13 Correct 205 ms 29580 KB Output is correct
14 Correct 207 ms 29668 KB Output is correct
15 Correct 191 ms 27480 KB Output is correct
16 Correct 163 ms 27492 KB Output is correct
17 Correct 207 ms 29408 KB Output is correct
18 Correct 171 ms 29672 KB Output is correct
19 Correct 125 ms 27492 KB Output is correct
20 Correct 184 ms 30212 KB Output is correct
21 Correct 141 ms 27684 KB Output is correct
22 Correct 113 ms 27692 KB Output is correct
23 Correct 160 ms 26948 KB Output is correct
24 Correct 160 ms 27412 KB Output is correct
25 Correct 208 ms 32736 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 11720 KB Output is correct
2 Correct 22 ms 11780 KB Output is correct
3 Correct 187 ms 28004 KB Output is correct
4 Correct 202 ms 28500 KB Output is correct
5 Correct 294 ms 29608 KB Output is correct
6 Correct 225 ms 29764 KB Output is correct
7 Correct 218 ms 29736 KB Output is correct
8 Correct 211 ms 29764 KB Output is correct
9 Correct 188 ms 21144 KB Output is correct
10 Correct 176 ms 20928 KB Output is correct
11 Correct 148 ms 22940 KB Output is correct
12 Correct 214 ms 27080 KB Output is correct
13 Correct 228 ms 28472 KB Output is correct
14 Correct 233 ms 29920 KB Output is correct
15 Correct 262 ms 29660 KB Output is correct
16 Correct 187 ms 22788 KB Output is correct
17 Correct 134 ms 27284 KB Output is correct
18 Correct 130 ms 27488 KB Output is correct
19 Correct 156 ms 27392 KB Output is correct
20 Correct 132 ms 27508 KB Output is correct
21 Correct 255 ms 30252 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11696 KB Output is correct
2 Correct 25 ms 11832 KB Output is correct
3 Correct 223 ms 28176 KB Output is correct
4 Correct 175 ms 28416 KB Output is correct
5 Correct 204 ms 28688 KB Output is correct
6 Correct 255 ms 29740 KB Output is correct
7 Correct 150 ms 28164 KB Output is correct
8 Correct 205 ms 28272 KB Output is correct
9 Correct 190 ms 28684 KB Output is correct
10 Correct 252 ms 29736 KB Output is correct
11 Correct 215 ms 29808 KB Output is correct
12 Correct 243 ms 29792 KB Output is correct
13 Correct 164 ms 22984 KB Output is correct
14 Correct 142 ms 20972 KB Output is correct
15 Correct 176 ms 23116 KB Output is correct
16 Correct 189 ms 20980 KB Output is correct
17 Correct 177 ms 23032 KB Output is correct
18 Correct 147 ms 21008 KB Output is correct
19 Correct 241 ms 27044 KB Output is correct
20 Correct 238 ms 28332 KB Output is correct
21 Correct 252 ms 29832 KB Output is correct
22 Correct 219 ms 29716 KB Output is correct
23 Correct 264 ms 29888 KB Output is correct
24 Correct 251 ms 29828 KB Output is correct
25 Correct 254 ms 29660 KB Output is correct
26 Correct 271 ms 29636 KB Output is correct
27 Correct 177 ms 27412 KB Output is correct
28 Correct 165 ms 27232 KB Output is correct
29 Correct 166 ms 27712 KB Output is correct
30 Correct 156 ms 27572 KB Output is correct
31 Correct 155 ms 27400 KB Output is correct
32 Correct 131 ms 27212 KB Output is correct
33 Correct 148 ms 27660 KB Output is correct
34 Correct 136 ms 27324 KB Output is correct
35 Correct 138 ms 27456 KB Output is correct
36 Correct 126 ms 27132 KB Output is correct
37 Correct 166 ms 27564 KB Output is correct
38 Correct 129 ms 27476 KB Output is correct
39 Correct 253 ms 30368 KB Output is correct
40 Correct 243 ms 30732 KB Output is correct
41 Correct 232 ms 30012 KB Output is correct
42 Correct 249 ms 30228 KB Output is correct