oj.uz

Submission #966553

# Submission time Handle Problem Language Result Execution time Memory
966553 2024-04-20T03:48:45 Z Warinchai Highway Tolls (IOI18_highway) C++14
51 / 100
 142 ms 18816 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;
        //cerr<<x<<" "<<lv<<"\n";
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        dis1[x].first=lv;
        for(auto z:adj[x])if(!dis1[z.first].first&&z.first!=bg)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;
        //cerr<<x<<" "<<lv<<"\n";
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        dis2[x].first=lv;
        for(auto z:adj[x])if(!dis2[z.first].first&&z.first!=ed)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<<" ";
        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;
    st=0,en=side1.size()-1;
    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";*/
    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:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     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 1 ms 6148 KB Output is correct
2 Correct 2 ms 6144 KB Output is correct
3 Correct 2 ms 6148 KB Output is correct
4 Correct 2 ms 6148 KB Output is correct
5 Correct 2 ms 6396 KB Output is correct
6 Correct 2 ms 6148 KB Output is correct
7 Correct 2 ms 6140 KB Output is correct
8 Correct 2 ms 6140 KB Output is correct
9 Correct 2 ms 6144 KB Output is correct
10 Correct 2 ms 6140 KB Output is correct
11 Correct 2 ms 6148 KB Output is correct
12 Correct 1 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 17 ms 7068 KB Output is correct
3 Correct 95 ms 13900 KB Output is correct
4 Correct 99 ms 14336 KB Output is correct
5 Correct 110 ms 14096 KB Output is correct
6 Correct 119 ms 14092 KB Output is correct
7 Correct 105 ms 14392 KB Output is correct
8 Correct 129 ms 13980 KB Output is correct
9 Correct 119 ms 14120 KB Output is correct
10 Correct 95 ms 13916 KB Output is correct
11 Correct 104 ms 14684 KB Output is correct
12 Correct 101 ms 14920 KB Output is correct
13 Correct 132 ms 14880 KB Output is correct
14 Correct 135 ms 14676 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7520 KB Output is correct
2 Correct 26 ms 8652 KB Output is correct
3 Correct 35 ms 10212 KB Output is correct
4 Correct 90 ms 16508 KB Output is correct
5 Correct 93 ms 16972 KB Output is correct
6 Correct 100 ms 17856 KB Output is correct
7 Correct 89 ms 18816 KB Output is correct
8 Correct 94 ms 17408 KB Output is correct
9 Correct 103 ms 17532 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6200 KB Output is correct
2 Correct 17 ms 6992 KB Output is correct
3 Correct 96 ms 12368 KB Output is correct
4 Correct 110 ms 13856 KB Output is correct
5 Correct 95 ms 14356 KB Output is correct
6 Correct 95 ms 13840 KB Output is correct
7 Correct 108 ms 14096 KB Output is correct
8 Correct 142 ms 13932 KB Output is correct
9 Correct 96 ms 14288 KB Output is correct
10 Correct 125 ms 13880 KB Output is correct
11 Correct 103 ms 14420 KB Output is correct
12 Correct 133 ms 15380 KB Output is correct
13 Correct 127 ms 14708 KB Output is correct
14 Correct 141 ms 14352 KB Output is correct
15 Correct 95 ms 13904 KB Output is correct
16 Correct 100 ms 13880 KB Output is correct
17 Correct 113 ms 14932 KB Output is correct
18 Correct 114 ms 14888 KB Output is correct
19 Correct 114 ms 14108 KB Output is correct
20 Correct 100 ms 15296 KB Output is correct
21 Correct 109 ms 14492 KB Output is correct
22 Correct 102 ms 14916 KB Output is correct
23 Correct 115 ms 13888 KB Output is correct
24 Correct 102 ms 14100 KB Output is correct
25 Correct 100 ms 18320 KB Output is correct

Subtask #5
0 / 18.0

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