oj.uz

Submission #955187

# Submission time Handle Problem Language Result Execution time Memory
955187 2024-03-29T15:31:35 Z MarwenElarbi Railway Trip 2 (JOI22_ho_t4) C++17
19 / 100
 2000 ms 14232 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 2e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
vi adj[nax];
int main(){
    optimise;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    //setIO("dec");
    int n,k;
    cin>>n>>k;
    int m;
    cin>>m;
    int a[n+1];
    int b[n+1];
    for (int i = 0; i <= n; ++i)
    {
        a[i]=0;
        b[i]=1e9;
    }
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        if(x<y) a[x]=max(a[x],y);
        else b[x]=min(b[x],y);
    }
    multiset<int> st;
    int mx[n+1];
    int mn[n+1];
    for (int i = 0; i <= n; ++i)
    {
        if(i>=k){
            st.erase(st.find(a[i-k]));
        }
        st.insert(a[i]);
        mx[i]=max(i,(*--st.end()));
    }
    st.clear();
    for (int i = n; i >= 0; --i)
    {
        if(i<=n-k){
            st.erase(st.find(b[i+k]));
        }
        st.insert(b[i]);
        //cout <<*st.begin()<<endl;
        mn[i]=min(i,(*st.begin()));
    }
    int q;
    cin>>q;
    int dis[n+1];
    while(q--){
        int s,t;
        cin>>s>>t;
        queue<int> q;
        q.push(s);
        for (int i = 0; i <= n; ++i)
        {
            dis[i]=1e9;
        }
        dis[s]=0;
        bool test=false;
        while(!q.empty()){
            int node=q.front();
            q.pop();
            //cout <<node<<" "<<mn[node]<<" "<<mx[node]<<endl;
            if(node==t){
                cout << dis[node]<<'\n';
                test=true;
                break;
            }
            for (int i = mn[node]; i <=mx[node] ; ++i)
            {
                if(dis[i]<=dis[node]+1) continue;
                q.push(i);
                dis[i]=dis[node]+1;
            }
        }
        if(!test){
            cout <<-1<<'\n';
        }
    }
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 14 ms 5172 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 14 ms 5172 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 862 ms 5168 KB Output is correct
14 Correct 331 ms 5424 KB Output is correct
15 Correct 2 ms 4952 KB Output is correct
16 Correct 1271 ms 5248 KB Output is correct
17 Correct 7 ms 4956 KB Output is correct
18 Correct 1943 ms 5276 KB Output is correct
19 Correct 1720 ms 5460 KB Output is correct
20 Execution timed out 2017 ms 5228 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 7208 KB Output is correct
2 Correct 405 ms 7004 KB Output is correct
3 Correct 1561 ms 7228 KB Output is correct
4 Correct 120 ms 8060 KB Output is correct
5 Correct 1650 ms 11892 KB Output is correct
6 Correct 32 ms 9300 KB Output is correct
7 Correct 109 ms 14232 KB Output is correct
8 Correct 193 ms 10768 KB Output is correct
9 Correct 46 ms 13140 KB Output is correct
10 Correct 44 ms 9372 KB Output is correct
11 Correct 49 ms 13860 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 12028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2020 ms 8520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 14 ms 5172 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 862 ms 5168 KB Output is correct
14 Correct 331 ms 5424 KB Output is correct
15 Correct 2 ms 4952 KB Output is correct
16 Correct 1271 ms 5248 KB Output is correct
17 Correct 7 ms 4956 KB Output is correct
18 Correct 1943 ms 5276 KB Output is correct
19 Correct 1720 ms 5460 KB Output is correct
20 Execution timed out 2017 ms 5228 KB Time limit exceeded
21 Halted 0 ms 0 KB -