oj.uz

Submission #235997

# Submission time Handle Problem Language Result Execution time Memory
235997 2020-05-30T16:03:10 Z laoriu Highway Tolls (IOI18_highway) C++14
51 / 100
 232 ms 26812 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
typedef pair <int,int> pp;
int n,m,l,ll,vs[200002],D[2][200002];
vector <pp> P[200002],adj[200002],A[200002];
pp B[200002];
vector <int> ds,sub[2],w;
int ss,tt,aa,bb;

void build_tree(int x,int u,int v)
{
    memset(vs,0,sizeof(vs));
    queue <int> q;
    adj[u].push_back({v,x});adj[v].push_back({u,x});
    q.push(u);q.push(v);vs[u]=vs[v]=1;ds.push_back(x);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<A[u].size();i++)
        {
            int v=A[u][i].first;
            int x=A[u][i].second;
            if (vs[v]==1) continue;
            adj[u].push_back({v,x});
            vs[v]=1;
            ds.push_back(x);
            q.push(v);
        }
    }
}
void bfs(int p,int u,int ban)
{
    queue <int> q;
    for (int i=0;i<n;i++)
        D[p][i]=1e9;
    memset(vs,0,sizeof(vs));
    q.push(u);D[p][u]=0;vs[u]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i].first;
            int x=adj[u][i].second;
            if (vs[v]==1||x==ban) continue;
            vs[v]=1;D[p][v]=D[p][u]+1;
            sub[p].push_back(x);
            q.push(v);
        }
    }
}
int find1(int p,int s,int l)
{
    if (l==0) return s;
    vector <int> X;
    for (int i=0;i<sub[p].size();i++)
    {
        int u=B[sub[p][i]].first;
        int v=B[sub[p][i]].second;
        if (D[p][u]>D[p][v]) swap(u,v);
        if (D[p][u]==l-1&&D[p][v]==l)
        {
            X.push_back(sub[p][i]);
        }
    }
    int d=0;int c=X.size()-1;
    vector <int> w;w.resize(m,0);
    int ans=0;
    while (d<=c)
    {
        int mid=(d+c)/2;
        for (int i=0;i<m;i++)
            w[i]=1;
        for (int i=0;i<=mid;i++)
            w[X[i]]=0;
        if (ask(w)<(long long)bb*ll)
        {
            c=mid-1;
            ans=X[mid];
        }
        else d=mid+1;
    }
    int u=B[ans].first;int v=B[ans].second;
    if (D[p][u]==l) return u;else return v;
}
void find_pair(int n,vector <int> U,vector <int> V,int a,int b)
{
    aa=a;bb=b;
    m=U.size();
    for (int i=0;i<U.size();i++)
    {
        A[U[i]].push_back({V[i],i});
        A[V[i]].push_back({U[i],i});
        B[i]={U[i],V[i]};
    }
    w.resize(m,0);
    long long t=ask(w);l=t/a;ll=l;
    int d=0;int c=m-1;int x;
    while (d<=c)
    {
        int mid=(d+c)/2;
        for (int i=0;i<m;i++)
            if (i<=mid) w[i]=0;else w[i]=1;
        if (ask(w)==t)
        {
            x=mid;
            c=mid-1;
        }
        else d=mid+1;
    }
    int u=U[x];int v=V[x];

    build_tree(x,u,v);
    bfs(0,u,x);bfs(1,v,x);
    for (int i=0;i<m;i++) w[i]=1;
    for (int i=0;i<sub[0].size();i++)
        w[sub[0][i]]=0;
    int l1;
    t=ask(w);
    for (int i=0;i<=l-1;i++)
        if ((long long) a*i+(long long) b*(l-i)==t) l1=i;
    int l2=l-1-l1;
    //cout<<l1<<' '<<l2<<endl;
    answer(find1(0,u,l1),find1(1,v,l2));
}

Compilation message

highway.cpp: In function 'void build_tree(int, int, int)':
highway.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<A[u].size();i++)
                      ~^~~~~~~~~~~~
highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<adj[u].size();i++)
                      ~^~~~~~~~~~~~~~
highway.cpp: In function 'int find1(int, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[p].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<U.size();i++)
                  ~^~~~~~~~~
highway.cpp:120:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[0].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp:128:11: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     answer(find1(0,u,l1),find1(1,v,l2));
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:115:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int u=U[x];int v=V[x];
              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 13 ms 15232 KB Output is correct
3 Correct 13 ms 15232 KB Output is correct
4 Correct 13 ms 15232 KB Output is correct
5 Correct 13 ms 15232 KB Output is correct
6 Correct 14 ms 15232 KB Output is correct
7 Correct 13 ms 15256 KB Output is correct
8 Correct 13 ms 15232 KB Output is correct
9 Correct 13 ms 15232 KB Output is correct
10 Correct 13 ms 15232 KB Output is correct
11 Correct 13 ms 15232 KB Output is correct
12 Correct 13 ms 15208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15360 KB Output is correct
2 Correct 25 ms 16248 KB Output is correct
3 Correct 172 ms 24740 KB Output is correct
4 Correct 142 ms 24756 KB Output is correct
5 Correct 150 ms 24396 KB Output is correct
6 Correct 172 ms 24516 KB Output is correct
7 Correct 166 ms 24564 KB Output is correct
8 Correct 147 ms 24744 KB Output is correct
9 Correct 162 ms 24788 KB Output is correct
10 Correct 156 ms 24688 KB Output is correct
11 Correct 154 ms 25420 KB Output is correct
12 Correct 150 ms 25308 KB Output is correct
13 Correct 153 ms 25180 KB Output is correct
14 Correct 150 ms 25276 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16248 KB Output is correct
2 Correct 34 ms 17352 KB Output is correct
3 Correct 48 ms 18556 KB Output is correct
4 Correct 117 ms 25068 KB Output is correct
5 Correct 117 ms 24992 KB Output is correct
6 Correct 119 ms 24864 KB Output is correct
7 Correct 120 ms 24920 KB Output is correct
8 Correct 120 ms 25028 KB Output is correct
9 Correct 116 ms 24984 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15360 KB Output is correct
2 Correct 25 ms 16248 KB Output is correct
3 Correct 120 ms 22532 KB Output is correct
4 Correct 165 ms 24768 KB Output is correct
5 Correct 154 ms 24684 KB Output is correct
6 Correct 154 ms 24428 KB Output is correct
7 Correct 148 ms 24316 KB Output is correct
8 Correct 156 ms 24420 KB Output is correct
9 Correct 157 ms 24724 KB Output is correct
10 Correct 187 ms 24460 KB Output is correct
11 Correct 199 ms 25300 KB Output is correct
12 Correct 191 ms 25284 KB Output is correct
13 Correct 192 ms 25256 KB Output is correct
14 Correct 190 ms 25444 KB Output is correct
15 Correct 173 ms 24440 KB Output is correct
16 Correct 157 ms 24408 KB Output is correct
17 Correct 205 ms 25328 KB Output is correct
18 Correct 186 ms 25284 KB Output is correct
19 Correct 232 ms 24416 KB Output is correct
20 Correct 161 ms 25264 KB Output is correct
21 Correct 196 ms 24092 KB Output is correct
22 Correct 131 ms 24092 KB Output is correct
23 Correct 188 ms 24344 KB Output is correct
24 Correct 169 ms 24380 KB Output is correct
25 Correct 206 ms 25200 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16376 KB Output is correct
2 Correct 31 ms 16376 KB Output is correct
3 Correct 207 ms 25340 KB Output is correct
4 Correct 210 ms 25456 KB Output is correct
5 Incorrect 226 ms 26812 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16332 KB Output is correct
2 Correct 29 ms 16376 KB Output is correct
3 Correct 186 ms 24972 KB Output is correct
4 Incorrect 214 ms 25544 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -