oj.uz

Submission #966533

# Submission time Handle Problem Language Result Execution time Memory
966533 2024-04-20T03:08:00 Z Warinchai Highway Tolls (IOI18_highway) C++14
51 / 100
 135 ms 18596 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){
    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;
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        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;
    }
    q.push({ed,0});
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        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;
        if(dis1[i].first<dis2[i].first){
            adj[dis1[i].second.second].push_back({i,dis1[i].second.first});
        }else{
            adj[dis1[i].second.second].push_back({i,dis2[i].second.first});
        }
    }
    for(int i=0;i<u.size();i++)temp.push_back(0);
    //temp[ans]=1;
    //assert(ask(temp)>cost);
    dfs(bg,side1,node1,ed,ans);
    for(int i=0;i<n;i++)vis[i]=0;
    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:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=m+1;i<u.size();i++)temp.push_back(0);
      |                       ~^~~~~~~~~
highway.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<u.size();i++)temp.push_back(0);
      |                 ~^~~~~~~~~
highway.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     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:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     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:116:30: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |     answer(node1[n1],node2[n2]);
      |                              ^
highway.cpp:116:20: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  116 |     answer(node1[n1],node2[n2]);
      |                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6144 KB Output is correct
2 Correct 2 ms 6148 KB Output is correct
3 Correct 1 ms 6144 KB Output is correct
4 Correct 2 ms 6148 KB Output is correct
5 Correct 2 ms 6136 KB Output is correct
6 Correct 2 ms 6148 KB Output is correct
7 Correct 2 ms 6136 KB Output is correct
8 Correct 1 ms 6144 KB Output is correct
9 Correct 2 ms 6232 KB Output is correct
10 Correct 2 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 15 ms 7064 KB Output is correct
3 Correct 126 ms 13940 KB Output is correct
4 Correct 131 ms 14088 KB Output is correct
5 Correct 123 ms 14116 KB Output is correct
6 Correct 97 ms 13880 KB Output is correct
7 Correct 111 ms 14092 KB Output is correct
8 Correct 93 ms 13896 KB Output is correct
9 Correct 104 ms 14112 KB Output is correct
10 Correct 110 ms 13928 KB Output is correct
11 Correct 124 ms 14016 KB Output is correct
12 Correct 130 ms 14940 KB Output is correct
13 Correct 99 ms 14624 KB Output is correct
14 Correct 97 ms 15108 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7524 KB Output is correct
2 Correct 19 ms 8676 KB Output is correct
3 Correct 28 ms 10272 KB Output is correct
4 Correct 75 ms 16724 KB Output is correct
5 Correct 95 ms 16848 KB Output is correct
6 Correct 93 ms 18084 KB Output is correct
7 Correct 100 ms 18596 KB Output is correct
8 Correct 92 ms 17504 KB Output is correct
9 Correct 85 ms 17292 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 12 ms 6992 KB Output is correct
3 Correct 87 ms 12364 KB Output is correct
4 Correct 135 ms 14116 KB Output is correct
5 Correct 102 ms 14372 KB Output is correct
6 Correct 129 ms 14364 KB Output is correct
7 Correct 104 ms 14112 KB Output is correct
8 Correct 134 ms 14064 KB Output is correct
9 Correct 100 ms 13800 KB Output is correct
10 Correct 115 ms 14276 KB Output is correct
11 Correct 112 ms 14636 KB Output is correct
12 Correct 95 ms 15372 KB Output is correct
13 Correct 121 ms 14692 KB Output is correct
14 Correct 104 ms 14588 KB Output is correct
15 Correct 93 ms 14184 KB Output is correct
16 Correct 84 ms 13880 KB Output is correct
17 Correct 98 ms 14716 KB Output is correct
18 Correct 132 ms 15092 KB Output is correct
19 Correct 101 ms 13888 KB Output is correct
20 Correct 100 ms 15780 KB Output is correct
21 Correct 79 ms 14436 KB Output is correct
22 Correct 91 ms 14668 KB Output is correct
23 Correct 101 ms 14088 KB Output is correct
24 Correct 134 ms 14136 KB Output is correct
25 Correct 115 ms 18336 KB Output is correct

Subtask #5
0 / 18.0

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