oj.uz

Submission #140330

# Submission time Handle Problem Language Result Execution time Memory
140330 2019-08-02T14:47:06 Z XmtosX Highway Tolls (IOI18_highway) C++17
51 / 100
 1433 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=90005;
int n,m,par[MAXN];
vector <int> v[MAXN];
vector <pair<int,int> > vv;
map <pair<int,int>, int> r;
long long ANS;
bool block[MAXN];
void dfs (int x,int p,int l)
{
    vv.push_back({l,x});
    par[x]=p;
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p&&!block[v[x][i]])
        {
            dfs(v[x][i],x,l+1);
        }
    }
}
void find_pair (int N, vector<int> U, vector<int> V, int A, int B)
{
    n=N;
    m=U.size();
    vector<int> w;
    w.resize(m);
    ANS=ask(w);
    int low=0,high=m-1,ans,mid;
    while (low<=high)
    {
        mid=(high+low)/2;
        if (low==high)
        {
            ans=mid;
            break;
        }
        if (mid==low)
            mid++;
        for (int i=0;i<m;i++)
            w[i]=0;
        for (int i=mid;i<=high;i++)
        {
            w[i]=1;
        }
        if (ANS!=ask(w))
        {
            low=mid;
        }
        else
            high=mid-1;
    }
    for (int i=0;i<m;i++)
    {
        v[U[i]].push_back(V[i]);
        v[V[i]].push_back(U[i]);
        r[{U[i],V[i]}]=i;
        r[{V[i],U[i]}]=i;
    }
    block[U[ans]]=1;
    block[V[ans]]=1;
    int an[2];
    int u[2]={U[ans],V[ans]};
    for (int q=0;q<2;q++)
    {
        vv.clear();
        dfs(u[q],u[1-q],1);
        if (vv.size()==1)
        {
            an[q]=vv[0].second;
            continue;
        }
        low=0,high=vv.size(),mid,ans=-1;
        while (low<=high)
        {
            for (int i=0;i<w.size();i++)
                w[i]=0;
            mid=(low+high)/2;
            for (int i=mid;i<vv.size();i++)
            {
                int a=vv[i].second;
                w[r[{a,par[a]}]]=1;
            }
            if (ask(w)!=ANS)
            {
                ans=vv[mid].second;
                low=mid+1;
            }
            else
                high=mid-1;
        }
        an[q]=ans;
    }
    answer(an[0],an[1]);
}

Compilation message

highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:74:39: warning: right operand of comma operator has no effect [-Wunused-value]
         low=0,high=vv.size(),mid,ans=-1;
                                       ^
highway.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=0;i<w.size();i++)
                          ~^~~~~~~~~
highway.cpp:80:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=mid;i<vv.size();i++)
                            ~^~~~~~~~~~
highway.cpp:61:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     block[U[ans]]=1;
                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2344 KB Output is correct
2 Correct 4 ms 2440 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2528 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 5 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2572 KB Output is correct
10 Correct 4 ms 2428 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2552 KB Output is correct
2 Correct 57 ms 4464 KB Output is correct
3 Correct 488 ms 19876 KB Output is correct
4 Correct 942 ms 19920 KB Output is correct
5 Correct 1228 ms 19824 KB Output is correct
6 Correct 954 ms 19820 KB Output is correct
7 Correct 664 ms 19864 KB Output is correct
8 Correct 1302 ms 19900 KB Output is correct
9 Correct 992 ms 19884 KB Output is correct
10 Correct 1299 ms 19916 KB Output is correct
11 Correct 1271 ms 20660 KB Output is correct
12 Correct 1044 ms 21500 KB Output is correct
13 Correct 1091 ms 21240 KB Output is correct
14 Correct 1191 ms 21488 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4964 KB Output is correct
2 Correct 83 ms 7076 KB Output is correct
3 Correct 132 ms 9820 KB Output is correct
4 Correct 514 ms 22548 KB Output is correct
5 Correct 502 ms 22876 KB Output is correct
6 Correct 358 ms 24108 KB Output is correct
7 Correct 490 ms 24888 KB Output is correct
8 Correct 395 ms 22956 KB Output is correct
9 Correct 517 ms 23764 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2600 KB Output is correct
2 Correct 55 ms 4388 KB Output is correct
3 Correct 310 ms 16356 KB Output is correct
4 Correct 1366 ms 19820 KB Output is correct
5 Correct 1358 ms 19932 KB Output is correct
6 Correct 409 ms 19844 KB Output is correct
7 Correct 1277 ms 19948 KB Output is correct
8 Correct 415 ms 19900 KB Output is correct
9 Correct 813 ms 19468 KB Output is correct
10 Correct 1239 ms 19856 KB Output is correct
11 Correct 576 ms 20928 KB Output is correct
12 Correct 959 ms 21488 KB Output is correct
13 Correct 1092 ms 20804 KB Output is correct
14 Correct 1135 ms 20984 KB Output is correct
15 Correct 1433 ms 19868 KB Output is correct
16 Correct 1310 ms 19856 KB Output is correct
17 Correct 885 ms 21200 KB Output is correct
18 Correct 1309 ms 21312 KB Output is correct
19 Correct 1292 ms 19868 KB Output is correct
20 Correct 1311 ms 21988 KB Output is correct
21 Correct 819 ms 20080 KB Output is correct
22 Correct 535 ms 20120 KB Output is correct
23 Correct 702 ms 19696 KB Output is correct
24 Correct 619 ms 20024 KB Output is correct
25 Correct 447 ms 24372 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 428 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 431 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -