oj.uz

Submission #966147

# Submission time Handle Problem Language Result Execution time Memory
966147 2024-04-19T12:30:49 Z Warinchai Highway Tolls (IOI18_highway) C++14
51 / 100
 136 ms 15248 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100000];
void dfs(int u,vector<int>&x,vector<int>&nodes,int p,int val){
    x.push_back(val);
    nodes.push_back(u);
    for(auto v:adj[u])if(v.first!=p)dfs(v.first,x,nodes,u,v.second);
}
void subtree(int n,vector<int>u,vector<int>v,int a,int b,long long cost){
    //cerr<<"work\n";
    int st=0,en=u.size()-1,ans=0;
    while(st<=en){
        int m=(st+en)/2;
        //cerr<<"m:"<<m<<"  ";
        vector<int>temp;
        for(int i=0;i<=m;i++)temp.push_back(1);
        for(int i=m+1;i<n-1;i++)temp.push_back(0);
      //  cerr<<temp.size()<<"\n";
        long long tcost=ask(temp);
        //cerr<<tcost<<"\n";
        if(tcost>cost){
            en=m-1;
            ans=m;
        }else{
            st=m+1;
        }
    }
    int bg=u[ans];
    int ed=v[ans];
    //cerr<<bg<<" "<<ed<<"\n";
    vector<int>temp;
    vector<int>side1;
    vector<int>side2;
    vector<int>node1;
    vector<int>node2;
    for(int i=0;i<n-1;i++)temp.push_back(0);
    //temp[ans]=1;
    //assert(ask(temp)>cost);
    dfs(bg,side1,node1,ed,ans);
    dfs(ed,side2,node2,bg,ans);
    for(auto x:side1)temp[x]=1;
    long long cost1=ask(temp);
    for(auto x:side1)temp[x]=0;
    for(auto x:side2)temp[x]=1;
    long long cost2=ask(temp);
    for(int i=0;i<n-1;i++)temp[i]=0;
    int n1,n2;
    st=0,en=side1.size()-1;
    for(int i=0;i<n-1;i++)temp[i]=0;
  //  cerr<<"side1\n";
    //for(auto x:side1)cerr<<x<<" ";
//    cerr<<"\n";
    //cerr<<"side2\n";
    //for(auto x:side2)cerr<<x<<" ";
    //cerr<<"\n\n";
    while(st<=en){
        int m=(st+en)/2;
        for(int i=0;i<=m;i++)temp[side1[i]]=1;
        if(ask(temp)>=cost1){
            en=m-1;
            n1=m;
        }else{
            st=m+1;
        }
        for(int i=0;i<=m;i++)temp[side1[i]]=0;
    }
    st=0,en=side2.size()-1;
    while(st<=en){
        int m=(st+en)/2;
        for(int i=0;i<=m;i++)temp[side2[i]]=1;
        if(ask(temp)>=cost2){
            en=m-1;
            n2=m;
        }else{
            st=m+1;
        }
        for(int i=0;i<=m;i++)temp[side2[i]]=0;
    }
    //cerr<<node1[n1]<<" "<<node2[n2]<<"\n";
    answer(node1[n1],node2[n2]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    //cerr<<"work\n";
    for(int i=0;i<U.size();i++){
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    vector<int>temp;
    for(int i=0;i<N-1;i++)temp.push_back(0);
    if(U.size()!=N-1)return answer(rand()%N,rand()%N);
    else return subtree(N,U,V,A,B,ask(temp));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:91:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     if(U.size()!=N-1)return answer(rand()%N,rand()%N);
      |        ~~~~~~~~^~~~~
highway.cpp: In function 'void subtree(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:81:30: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     answer(node1[n1],node2[n2]);
      |                              ^
highway.cpp:81:20: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     answer(node1[n1],node2[n2]);
      |                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 1 ms 2788 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2792 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2844 KB Output is correct
2 Correct 10 ms 3700 KB Output is correct
3 Correct 86 ms 10456 KB Output is correct
4 Correct 92 ms 10676 KB Output is correct
5 Correct 86 ms 10712 KB Output is correct
6 Correct 95 ms 10696 KB Output is correct
7 Correct 106 ms 10668 KB Output is correct
8 Correct 100 ms 10488 KB Output is correct
9 Correct 87 ms 11144 KB Output is correct
10 Correct 100 ms 10676 KB Output is correct
11 Correct 108 ms 10684 KB Output is correct
12 Correct 95 ms 11804 KB Output is correct
13 Correct 102 ms 11556 KB Output is correct
14 Correct 106 ms 11552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4144 KB Output is correct
2 Correct 28 ms 5540 KB Output is correct
3 Correct 38 ms 6720 KB Output is correct
4 Correct 79 ms 13124 KB Output is correct
5 Correct 77 ms 13176 KB Output is correct
6 Correct 77 ms 14508 KB Output is correct
7 Correct 117 ms 15248 KB Output is correct
8 Correct 77 ms 13660 KB Output is correct
9 Correct 95 ms 13940 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2852 KB Output is correct
2 Correct 10 ms 3688 KB Output is correct
3 Correct 74 ms 8936 KB Output is correct
4 Correct 87 ms 10764 KB Output is correct
5 Correct 80 ms 10452 KB Output is correct
6 Correct 92 ms 10516 KB Output is correct
7 Correct 88 ms 10532 KB Output is correct
8 Correct 100 ms 10492 KB Output is correct
9 Correct 100 ms 10644 KB Output is correct
10 Correct 136 ms 10708 KB Output is correct
11 Correct 107 ms 11088 KB Output is correct
12 Correct 89 ms 12252 KB Output is correct
13 Correct 100 ms 11392 KB Output is correct
14 Correct 92 ms 10996 KB Output is correct
15 Correct 96 ms 10484 KB Output is correct
16 Correct 80 ms 10676 KB Output is correct
17 Correct 88 ms 11348 KB Output is correct
18 Correct 83 ms 11552 KB Output is correct
19 Correct 84 ms 10520 KB Output is correct
20 Correct 98 ms 11960 KB Output is correct
21 Correct 71 ms 10700 KB Output is correct
22 Correct 79 ms 10644 KB Output is correct
23 Correct 80 ms 10404 KB Output is correct
24 Correct 102 ms 10680 KB Output is correct
25 Correct 88 ms 14936 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3416 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3416 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -