oj.uz

Submission #966565

# Submission time Handle Problem Language Result Execution time Memory
966565 2024-04-20T04:17:50 Z Warinchai Highway Tolls (IOI18_highway) C++14
51 / 100
 154 ms 18848 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100000];
int vis[100000];
void dfs(int u,vector<int>&x,vector<int>&nodes,int p,int val){
    //cerr<<u<<"\n";
    vis[u]=1;
    x.push_back(val);
    nodes.push_back(u);
    for(auto v:adj[u])if(!vis[v.first])dfs(v.first,x,nodes,u,v.second);
}
pair<int,pair<int,int> > dis1[100000],dis2[100000];
int to1[100000],to2[100000];
void subgraph(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<u.size();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;
        }
    }
    //cerr<<"work\n";
    int bg=u[ans];
    int ed=v[ans];
    //cerr<<bg<<" "<<ed<<"\n";
    queue<pair<int,int> >q;
    q.push({bg,0});
    dis1[bg].second.first=dis2[bg].second.first=ans;
    //cerr<<"dis1:\n";
    for(int i=0;i<n;i++)vis[i]=0;
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        //if(vis[x])continue;
        ///cerr<<x<<" "<<lv<<"\n";
        //vis[x]=1;
        dis1[x].first=lv;
        for(auto z:adj[x])if(!dis1[z.first].first&&z.first!=bg&&!vis[z.first])vis[z.first]=1,q.push({z.first,lv+1}),dis1[z.first].second.first=z.second,dis1[z.first].second.second=x;
    }
    for(int i=0;i<n;i++)vis[i]=0;
    q.push({ed,0});
    //cerr<<"dis2:\n";
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        //if(vis[x])continue;
        //cerr<<x<<" "<<lv<<"\n";
        //vis[x]=1;
        dis2[x].first=lv;
        for(auto z:adj[x])if(!dis2[z.first].first&&z.first!=ed&&!vis[z.first])vis[z.first]=1,q.push({z.first,lv+1}),dis2[z.first].second.first=z.second,dis2[z.first].second.second=x;
    }
    //for(int i=0;i<n;i++)cerr<<i<<" "<<dis1[i].first<<" "<<dis2[i].first<<"\n";
    vector<int>temp;
    vector<int>side1;
    vector<int>side2;
    vector<int>node1;
    vector<int>node2;
    for(int i=0;i<n;i++)adj[i].clear();
    for(int i=0;i<n;i++){
        if(i==bg||i==ed)continue;
        //cerr<<i<<":"<<dis1[i].first<<" "<<dis2[i].first<<"\n";
        if(dis1[i].first<dis2[i].first){
            adj[dis1[i].second.second].push_back({i,dis1[i].second.first});
            //cerr<<dis1[i].second.second<<"\n";
        }else{
            adj[dis2[i].second.second].push_back({i,dis2[i].second.first});
            //cerr<<dis2[i].second.second<<"\n";
        }
    }
    /*for(int i=0;i<n;i++){
        cerr<<i<<":\n";
        for(auto x:adj[i])cerr<<x.first<<" ";
        cerr<<"\n";
    }*/
    for(int i=0;i<u.size();i++)temp.push_back(0);
    //temp[ans]=1;
    //assert(ask(temp)>cost);
    //cerr<<"dfs1:\n";
    for(int i=0;i<n;i++)vis[i]=0;
    dfs(bg,side1,node1,ed,ans);
    for(int i=0;i<n;i++)vis[i]=0;
    //cerr<<"dfs2:\n";
    dfs(ed,side2,node2,bg,ans);
    for(int i=0;i<u.size();i++)temp[i]=1;
    long long cost1=ask(temp);
    long long cost2=ask(temp);
    int n1,n2;
    for(int i=0;i<u.size();i++)temp[i]=1;
    for(auto x:side1)temp[x]=0;
    //cerr<<"pass\n";
    //cerr<<"side1:\n";
    /*for(auto x:side1)cerr<<x<<" ";
    cerr<<"\n";
    cerr<<"side2:\n";
    for(auto x:side2)cerr<<x<<" ";
    cerr<<"\n";*/
    st=0,en=side1.size()-1;
    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;
    }
    for(int i=0;i<u.size();i++)temp[i]=1;
    for(auto x:side2)temp[x]=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<U.size();i++)temp.push_back(0);
    //if(U.size()!=N-1)return answer(rand()%N,rand()%N);
    subgraph(N,U,V,A,B,ask(temp));
}

Compilation message

highway.cpp: In function 'void subgraph(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=m+1;i<u.size();i++)temp.push_back(0);
      |                       ~^~~~~~~~~
highway.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<u.size();i++)temp.push_back(0);
      |                 ~^~~~~~~~~
highway.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i=0;i<U.size();i++)temp.push_back(0);
      |                 ~^~~~~~~~~
highway.cpp: In function 'void subgraph(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:138:30: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     answer(node1[n1],node2[n2]);
      |                              ^
highway.cpp:138:20: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     answer(node1[n1],node2[n2]);
      |                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6148 KB Output is correct
2 Correct 3 ms 6144 KB Output is correct
3 Correct 2 ms 6144 KB Output is correct
4 Correct 2 ms 6144 KB Output is correct
5 Correct 2 ms 6396 KB Output is correct
6 Correct 2 ms 6148 KB Output is correct
7 Correct 3 ms 6144 KB Output is correct
8 Correct 2 ms 6144 KB Output is correct
9 Correct 3 ms 6144 KB Output is correct
10 Correct 1 ms 6144 KB Output is correct
11 Correct 2 ms 6144 KB Output is correct
12 Correct 2 ms 6144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6196 KB Output is correct
2 Correct 16 ms 7068 KB Output is correct
3 Correct 129 ms 13880 KB Output is correct
4 Correct 105 ms 14084 KB Output is correct
5 Correct 91 ms 13892 KB Output is correct
6 Correct 119 ms 14092 KB Output is correct
7 Correct 94 ms 13928 KB Output is correct
8 Correct 97 ms 14116 KB Output is correct
9 Correct 111 ms 13876 KB Output is correct
10 Correct 92 ms 14104 KB Output is correct
11 Correct 134 ms 14480 KB Output is correct
12 Correct 102 ms 14916 KB Output is correct
13 Correct 89 ms 14632 KB Output is correct
14 Correct 106 ms 14900 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7504 KB Output is correct
2 Correct 20 ms 8912 KB Output is correct
3 Correct 34 ms 10076 KB Output is correct
4 Correct 125 ms 16496 KB Output is correct
5 Correct 77 ms 16556 KB Output is correct
6 Correct 79 ms 18096 KB Output is correct
7 Correct 114 ms 18848 KB Output is correct
8 Correct 94 ms 17056 KB Output is correct
9 Correct 98 ms 17572 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6196 KB Output is correct
2 Correct 15 ms 7224 KB Output is correct
3 Correct 106 ms 12568 KB Output is correct
4 Correct 108 ms 14048 KB Output is correct
5 Correct 114 ms 13900 KB Output is correct
6 Correct 107 ms 13868 KB Output is correct
7 Correct 88 ms 14120 KB Output is correct
8 Correct 122 ms 13840 KB Output is correct
9 Correct 103 ms 14032 KB Output is correct
10 Correct 96 ms 13872 KB Output is correct
11 Correct 100 ms 14392 KB Output is correct
12 Correct 154 ms 15356 KB Output is correct
13 Correct 110 ms 15460 KB Output is correct
14 Correct 123 ms 14128 KB Output is correct
15 Correct 100 ms 14516 KB Output is correct
16 Correct 86 ms 14132 KB Output is correct
17 Correct 110 ms 14684 KB Output is correct
18 Correct 100 ms 15088 KB Output is correct
19 Correct 92 ms 14112 KB Output is correct
20 Correct 102 ms 15356 KB Output is correct
21 Correct 97 ms 14624 KB Output is correct
22 Correct 105 ms 14436 KB Output is correct
23 Correct 94 ms 14308 KB Output is correct
24 Correct 93 ms 14096 KB Output is correct
25 Correct 129 ms 18152 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 7060 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 11 ms 7016 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -