Submission #919121

#	Time	Username	Problem	Language	Result	Execution time	Memory
919121		velislavgarkov	Highway Tolls (IOI18_highway)	C++14	5 / 100	109 ms	8468 KiB

highway

#include "highway.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=1e5+10;
vector <pair <int,int> > v[MAXN], dist;
vector <int> w;
bool used[MAXN];
int edge;
long long a, b, path;
int n;
void find_tree(int x) {
    used[x]=true;
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (used[i.first]) continue;
        w[i.second]=1;
        find_tree(i.first);
    }
}
void dfs(int x, int d) {
    used[x]=true;
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (used[i.first]) continue;
        if (d==1) {
            dist.push_back(i);
            continue;
        }
        dfs(i.first,d-1);
    }
}
int find_one(int start) {
    for (int i=0;i<n-1;i++) w[i]=0;
    memset(used,false,sizeof(used));
    find_tree(start);
    long long d=(ask(w)-path)/(b-a);
    if (d==0) return start;
    if (!dist.empty()) dist.clear();
    memset(used,false,sizeof(used));
    dfs(start,d);
    int l, r, mid;
    l=0; r=dist.size()-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[dist[i].second]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    return dist[l].first;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
    n=N; a=A; b=B;
    w.resize(n-1);
    for (int i=0;i<U.size();i++) {
        v[U[i]].push_back({V[i],i});
        v[V[i]].push_back({U[i],i});
    }
    for (int i=0;i<n-1;i++) w[i]=0;
    path=ask(w);
    //cout << path << endl;
    edge=-1;
    int ans1, ans2;
    /*
    int l, r, mid;
    l=0; r=n-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[i]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    edge=l;
    //cout << U[edge] << ' ' << V[edge] << endl;
    ans1=find_one(U[edge]);
    ans2=find_one(V[edge]);*/
    ans1=0;
    ans2=find_one(0);
    answer(ans1,ans2);    
}

Compilation message (stderr)

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

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