oj.uz

Submission #955182

# Submission time Handle Problem Language Result Execution time Memory
955182 2024-03-29T15:19:25 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(st.find(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(st.find(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]<<'\n';
                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<<'\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 5208 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 6 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 10 ms 5724 KB Output is correct
7 Correct 8 ms 5892 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 9 ms 5720 KB Output is correct
10 Correct 1 ms 4956 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 5208 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 6 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 10 ms 5724 KB Output is correct
7 Correct 8 ms 5892 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 9 ms 5720 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 777 ms 10860 KB Output is correct
14 Correct 277 ms 7256 KB Output is correct
15 Correct 4 ms 7004 KB Output is correct
16 Correct 1136 ms 13992 KB Output is correct
17 Correct 7 ms 5212 KB Output is correct
18 Correct 1832 ms 22124 KB Output is correct
19 Correct 1646 ms 20532 KB Output is correct
20 Execution timed out 2056 ms 21360 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 635 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 595 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 598 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 4 ms 5208 KB Output is correct
2 Correct 5 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 6 ms 5468 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 10 ms 5724 KB Output is correct
7 Correct 8 ms 5892 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 9 ms 5720 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 777 ms 10860 KB Output is correct
14 Correct 277 ms 7256 KB Output is correct
15 Correct 4 ms 7004 KB Output is correct
16 Correct 1136 ms 13992 KB Output is correct
17 Correct 7 ms 5212 KB Output is correct
18 Correct 1832 ms 22124 KB Output is correct
19 Correct 1646 ms 20532 KB Output is correct
20 Execution timed out 2056 ms 21360 KB Time limit exceeded
21 Halted 0 ms 0 KB -