oj.uz

Submission #955181

# Submission time Handle Problem Language Result Execution time Memory
955181 2024-03-29T15:17:08 Z MarwenElarbi Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 524288 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;
    for (int i = 0; i <= n; ++i)
    {
        if(i>=k){
            st.erase(a[i-k]);
        }
        st.insert(a[i]);
        for (int j = i+1; j <= (*--st.end()); ++j)
        {
            adj[i].pb(j);
            //cout <<i<<" "<<j<<endl;
        }
    }
    st.clear();
    for (int i = n; i >= 0; --i)
    {
        if(i<=n-k){
            st.erase(b[i+k]);
        }
        st.insert(b[i]);
        //cout <<*st.begin()<<endl;
        for (int j = i-1; j >= *st.begin(); --j)
        {
            //cout <<i<<" "<<j<<endl;
            adj[i].pb(j);
        }
    }
    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();
            if(node==t){
                cout << dis[node]<<endl;
                test=true;
                break;
            }
            for(auto u:adj[node]){
                if(dis[u]<=dis[node]+1) continue;
                q.push(u);
                dis[u]=dis[node]+1;
            }
        }
        if(!test){
            cout <<-1<<endl;
        }
    }
}

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 5 ms 5212 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 7 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 12 ms 5916 KB Output is correct
7 Correct 10 ms 5916 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 5156 KB Output is correct
12 Correct 4 ms 4960 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5212 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 7 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 12 ms 5916 KB Output is correct
7 Correct 10 ms 5916 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 5156 KB Output is correct
12 Correct 4 ms 4960 KB Output is correct
13 Correct 933 ms 10856 KB Output is correct
14 Correct 341 ms 7256 KB Output is correct
15 Correct 5 ms 7260 KB Output is correct
16 Correct 1387 ms 14112 KB Output is correct
17 Correct 10 ms 5208 KB Output is correct
18 Execution timed out 2033 ms 21848 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 572 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 548 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5212 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 7 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 12 ms 5916 KB Output is correct
7 Correct 10 ms 5916 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 5156 KB Output is correct
12 Correct 4 ms 4960 KB Output is correct
13 Correct 933 ms 10856 KB Output is correct
14 Correct 341 ms 7256 KB Output is correct
15 Correct 5 ms 7260 KB Output is correct
16 Correct 1387 ms 14112 KB Output is correct
17 Correct 10 ms 5208 KB Output is correct
18 Execution timed out 2033 ms 21848 KB Time limit exceeded
19 Halted 0 ms 0 KB -