oj.uz

답안 #955189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955189 2024-03-29T15:37:02 Z MarwenElarbi Railway Trip 2 (JOI22_ho_t4) C++17
19 / 100
 2000 ms 12368 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;
    //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){
            if(a[i-k]!=0) st.erase(st.find(a[i-k]));
        }
        if(a[i]!=0) st.insert(a[i]);
        if(st.size()) mx[i]=max(i,(*--st.end()));
        else mx[i]=i;
    }
    st.clear();
    for (int i = n; i >= 0; --i)
    {
        if(i<=n-k){
            if(b[i+k]!=1e9) st.erase(st.find(b[i+k]));
        }
        if(b[i]!=1e9) st.insert(b[i]);
        //cout <<*st.begin()<<endl;
        if(st.size()) mn[i]=min(i,(*st.begin()));
        else mn[i]=i;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 10 ms 4956 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 11 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 10 ms 4956 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 11 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 872 ms 5172 KB Output is correct
14 Correct 294 ms 5172 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 1297 ms 5208 KB Output is correct
17 Correct 7 ms 4956 KB Output is correct
18 Correct 1986 ms 5480 KB Output is correct
19 Correct 1834 ms 5456 KB Output is correct
20 Execution timed out 2067 ms 5408 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1192 ms 7200 KB Output is correct
2 Correct 412 ms 7104 KB Output is correct
3 Correct 1502 ms 7232 KB Output is correct
4 Correct 89 ms 7004 KB Output is correct
5 Correct 1663 ms 8632 KB Output is correct
6 Correct 31 ms 6952 KB Output is correct
7 Correct 111 ms 12368 KB Output is correct
8 Correct 171 ms 8536 KB Output is correct
9 Correct 36 ms 9044 KB Output is correct
10 Correct 40 ms 6996 KB Output is correct
11 Correct 39 ms 10064 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2069 ms 9308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2025 ms 7932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 10 ms 4956 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 11 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 872 ms 5172 KB Output is correct
14 Correct 294 ms 5172 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 1297 ms 5208 KB Output is correct
17 Correct 7 ms 4956 KB Output is correct
18 Correct 1986 ms 5480 KB Output is correct
19 Correct 1834 ms 5456 KB Output is correct
20 Execution timed out 2067 ms 5408 KB Time limit exceeded
21 Halted 0 ms 0 KB -