Submission #767115

#	Time	Username	Problem	Language	Result	Execution time	Memory
767115		DJeniUp	Highway Tolls (IOI18_highway)	C++17	0 / 100	14 ms	3668 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second
#define INF 10000000000000007

ll n,m,k,d[90007],fl[90007],d1[90007];

vector<pairll>v[90007],g;

priority_queue<pairll, vector<pairll>, greater<pairll> >q;

vector<int>f;

ll S(ll x){
    for(int i=0;i<m;i++){
        f[i]=0;
    }
    for(int i=0;i<=x;i++){
        for(int j=0;j<v[g[i].sc].size();j++){
            f[v[g[i].sc][j].fr]=1;
        }
    }
    ll k1=ask(f);
    if(k1!=k)return 1;
    return 0;
}

bool mcp(pairll g1, pairll g2){
    return g1.fr>g2.fr;
}

ll D(ll x){
    g.clear();
    for(int i=0;i<n;i++){
        d[i]=INF;
        d1[i]=INF;
    }
    d[x]=0;
    q.push({0,x});
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc;
        q.pop();
        for(int i=0;i<v[m2].size();i++){
            if(d[v[m2][i].sc]>m1+1){
                d[v[m2][i].sc]=m1+1;
                q.push({m1+1,v[m2][i].sc});
            }
        }
    }

    d1[x]=0;
    q.push({0,x});
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc;
        q.pop();
        if(f[m2]==0){
            for(int i=0;i<v[m2].size();i++){
                if(d1[v[m2][i].sc]>m1+1){
                    d1[v[m2][i].sc]=m1+1;
                    q.push({m1+1,v[m2][i].sc});
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(fl[i]!=1 && d[i]==d1[i])g.pb({d[i],i});
    }
    sort(g.begin(),g.end(),mcp);

    ll l=0;
    ll r=g.size()-1;
    while(l<r){
        ll m1=(l+r)/2;
        if(S(m1)==0)l=m1+1;
        else r=m1;
    }
    for(int i=0;i<l;i++){
        fl[g[i].sc]=1;
    }
    return g[l].sc;
}

void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
    n=_N;
    m=U.size();
    for(int i=0;i<m;i++){
        v[U[i]].pb({i,V[i]});
        v[V[i]].pb({i,U[i]});
        f.pb(0);
    }
    for(int i=0;i<n;i++)g.pb({0,i});
    k=ask(f);
    ll l=0;
    ll r=n-1;
    while(l<r){
        ll m1=(l+r)/2;
        if(S(m1)==0)l=m1+1;
        else r=m1;
    }
    for(int i=0;i<l;i++){
        fl[g[i].sc]=1;
    }
    ll s=D(l);
    ll t=D(s);
    //cout<<s<<" "<<t<<endl;
    answer(s,t);
    return ;
}

Compilation message (stderr)

highway.cpp: In function 'll S(ll)':
highway.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<v[g[i].sc].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'll D(ll)':
highway.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<v[m2].size();i++){
      |                     ~^~~~~~~~~~~~~
highway.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0;i<v[m2].size();i++){
      |                         ~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31