oj.uz

답안 #745853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745853 2023-05-21T08:48:17 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> tav;
vector<vector<int>> g;

main() {
    int N, Q; cin>>N>>Q;
    vector<int> s(N), e(N);
    for(int i=0; i<N; ++i)
    {
        cin>>s[i]>>e[i];
    }
    g.resize(N);
    tav.assign(N, vector<int>(N, INT_MAX/2));
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            if(i!=j && s[j]<=e[i] && e[i]<=e[j]) g[i].push_back(j);
        }
    }

    for(int i=0; i<N; ++i)
    {
        tav[i][i]=0;
        vector<int> volt(N, false);
        queue<int> q;
        q.push(i);
        while(!q.empty())
        {
            int a=q.front();
            q.pop();
            volt[a]=true;
            for(int to:g[a])
            {
                if(volt[to]) continue;
                volt[to]=true;
                q.push(to);
                tav[i][to]=tav[i][a]+1;
            }
        }
    }

    for(int i=0; i<Q; ++i)
    {
        int a, b; cin>>a>>b; a--; b--;
        if(tav[a][b]==INT_MAX/2)
        {
            cout<<"impossible\n";
            continue;
        }
        cout<<tav[a][b]<<'\n';
    }
    
    // for(auto x:tav)
    // {
    //     for(auto y:x) cerr<<y<<' ';
    //     cerr<<endl;
    // }
}

Compilation message

events.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 307 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 21 ms 8240 KB Output is correct
4 Correct 16 ms 8244 KB Output is correct
5 Correct 23 ms 8244 KB Output is correct
6 Correct 66 ms 9812 KB Output is correct
7 Correct 167 ms 11444 KB Output is correct
8 Correct 185 ms 13644 KB Output is correct
9 Correct 976 ms 16228 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 21 ms 8240 KB Output is correct
4 Correct 16 ms 8244 KB Output is correct
5 Correct 23 ms 8244 KB Output is correct
6 Correct 66 ms 9812 KB Output is correct
7 Correct 167 ms 11444 KB Output is correct
8 Correct 185 ms 13644 KB Output is correct
9 Correct 976 ms 16228 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 21 ms 8148 KB Output is correct
13 Correct 15 ms 8148 KB Output is correct
14 Correct 22 ms 8224 KB Output is correct
15 Correct 71 ms 9800 KB Output is correct
16 Correct 158 ms 11436 KB Output is correct
17 Correct 203 ms 13528 KB Output is correct
18 Correct 1002 ms 16240 KB Output is correct
19 Execution timed out 1581 ms 250828 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 21 ms 8240 KB Output is correct
4 Correct 16 ms 8244 KB Output is correct
5 Correct 23 ms 8244 KB Output is correct
6 Correct 66 ms 9812 KB Output is correct
7 Correct 167 ms 11444 KB Output is correct
8 Correct 185 ms 13644 KB Output is correct
9 Correct 976 ms 16228 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 19 ms 8244 KB Output is correct
13 Correct 14 ms 8228 KB Output is correct
14 Correct 22 ms 8148 KB Output is correct
15 Correct 62 ms 9812 KB Output is correct
16 Correct 144 ms 11436 KB Output is correct
17 Correct 184 ms 13528 KB Output is correct
18 Correct 976 ms 16228 KB Output is correct
19 Runtime error 266 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 290 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 307 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -