oj.uz

Submission #864195

# Submission time Handle Problem Language Result Execution time Memory
864195 2023-10-22T08:31:24 Z danikoynov Event Hopping (BOI22_events) C++14
30 / 100
 1500 ms 44744 KB 
    #include<bits/stdc++.h>
    #define debug true
    #ifdef DEVAL 
        #define debug false
    #endif
     
    using namespace std;
     
    const int maxn = 1e5 + 10;
     
    struct interval
    {
        int s, e, idx;
    }seg[maxn];
     
    int n, q;   
    pair < int, int > task[maxn];
    void read()
    {
        cin >> n >> q;
        for (int i = 1; i <= n; i ++)
        {
            cin >> seg[i].s >> seg[i].e;
            seg[i].idx = i;
        }
        for (int i = 1; i <= q; i ++)
        {
            cin >> task[i].first >> task[i].second;
        }
    }
     
     
    vector < int > adj[5010];
     
    int used[5010], dist[5010][5010];
    int my_queue[5010];
    void bfs(int start)
    {
        for (int i = 1; i <= n; i ++)
            used[i] = -1;
     
        used[start] = 0;
        int st = 1, en = 0;
        my_queue[++ en]  = start;
        while(st <= en)
        {
            int v = my_queue[st ++];
            for (int u : adj[v])
            {
                if (used[u] == - 1)
                {
                    used[u] = used[v] + 1;
                    my_queue[++ en] = u;
                }
            }
        }
    }
     
    void build_graph()
    {
        for (int i = 1; i <= n; i ++)
           for (int j = 1; j <= n; j ++)
            {
                if (seg[j].s <= seg[i].e && seg[i].e <= seg[j].e)
                    adj[i].push_back(j);
            }
    }
     
    void answer_queries()
    {
        for (int i = 1; i <= q; i ++)
        {
            if (dist[task[i].first][task[i].second] == -1)
                cout << "impossible" << endl;
            else
                cout << dist[task[i].first][task[i].second] << endl;
     
        }
    }
     
    void precalc()
    {
        for (int v = 1; v <= n; v ++)
        {
            bfs(v);
            for (int i = 1; i <= n; i ++)
                dist[v][i] = used[i];
        }
    }
     
    void speed()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }
    
    bool cmp(interval seg1, interval seg2)
    {
        return seg1.s < seg2.s;
    }

    const int maxlog = 21;

    int dp[maxlog][maxn], rev[maxn];
    void solve_no_intersect()
    {
        sort(seg + 1, seg + n + 1, cmp);
        int pt = n;
        for (int i = n; i > 0; i --)
        {
            while(seg[pt].s > seg[i].e)
                pt --;
            dp[0][i] = pt;
        }

        for (int j = 1; j < maxlog; j ++)
            for (int i = 1; i <= n; i ++)
            {
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }

        for (int i = 1; i <= n; i ++)
            rev[seg[i].idx] = i;
        for (int i = 1; i <= q; i ++)
        {
            int S = task[i].first, E = task[i].second;
            S = rev[S];
            E = rev[E];
            if (S > E)
            {
                cout << "impossible" << endl;
                continue;
            }

            if (S == E)
            {
                cout << 0 << endl;
                continue;
            }
        
            int jump = 0;
            for (int bit = maxlog - 1; bit >= 0; bit --)
            {
                if (dp[bit][S] < E)
                {
                    jump |= (1 << bit);
                    S = dp[bit][S];
                }
            }

            if (dp[0][S] < E)
                cout << "impossible" << endl;
            else
                cout << jump + 1 << endl;
        }

    }
    void solve()
    {
     
        read();
        if (n > 5000)
        {
            solve_no_intersect();
        }  
            else
            {
                build_graph();
                precalc();
            answer_queries(); 
       }   
    }
 
int main()
{
    speed();
    solve();
    return 0;
}
/**
3 2
1 2
2 3
3 4
1 3
2 3
 */

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 145 ms 13532 KB Output is correct
3 Correct 148 ms 13588 KB Output is correct
4 Correct 150 ms 13476 KB Output is correct
5 Incorrect 147 ms 13988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 25104 KB Output is correct
4 Correct 10 ms 25116 KB Output is correct
5 Correct 12 ms 25116 KB Output is correct
6 Correct 47 ms 25852 KB Output is correct
7 Correct 139 ms 26664 KB Output is correct
8 Correct 168 ms 27732 KB Output is correct
9 Correct 948 ms 29072 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 25104 KB Output is correct
4 Correct 10 ms 25116 KB Output is correct
5 Correct 12 ms 25116 KB Output is correct
6 Correct 47 ms 25852 KB Output is correct
7 Correct 139 ms 26664 KB Output is correct
8 Correct 168 ms 27732 KB Output is correct
9 Correct 948 ms 29072 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 12 ms 25092 KB Output is correct
13 Correct 10 ms 24924 KB Output is correct
14 Correct 12 ms 24924 KB Output is correct
15 Correct 47 ms 25860 KB Output is correct
16 Correct 139 ms 26448 KB Output is correct
17 Correct 168 ms 27712 KB Output is correct
18 Correct 950 ms 29328 KB Output is correct
19 Execution timed out 1561 ms 44744 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 25104 KB Output is correct
4 Correct 10 ms 25116 KB Output is correct
5 Correct 12 ms 25116 KB Output is correct
6 Correct 47 ms 25852 KB Output is correct
7 Correct 139 ms 26664 KB Output is correct
8 Correct 168 ms 27732 KB Output is correct
9 Correct 948 ms 29072 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6556 KB Output is correct
12 Correct 12 ms 24924 KB Output is correct
13 Correct 10 ms 24924 KB Output is correct
14 Correct 12 ms 24924 KB Output is correct
15 Correct 47 ms 25632 KB Output is correct
16 Correct 139 ms 26652 KB Output is correct
17 Correct 169 ms 27732 KB Output is correct
18 Correct 942 ms 29056 KB Output is correct
19 Correct 27 ms 12884 KB Output is correct
20 Correct 22 ms 12752 KB Output is correct
21 Incorrect 27 ms 12884 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 13396 KB Output is correct
2 Correct 147 ms 13308 KB Output is correct
3 Correct 150 ms 13324 KB Output is correct
4 Correct 149 ms 14008 KB Output is correct
5 Correct 153 ms 13792 KB Output is correct
6 Correct 154 ms 13652 KB Output is correct
7 Correct 157 ms 13628 KB Output is correct
8 Correct 152 ms 13652 KB Output is correct
9 Correct 25 ms 12888 KB Output is correct
10 Correct 147 ms 13136 KB Output is correct
11 Correct 146 ms 13136 KB Output is correct
12 Correct 147 ms 13124 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 145 ms 13532 KB Output is correct
3 Correct 148 ms 13588 KB Output is correct
4 Correct 150 ms 13476 KB Output is correct
5 Incorrect 147 ms 13988 KB Output isn't correct
6 Halted 0 ms 0 KB -