oj.uz

Submission #864194

# Submission time Handle Problem Language Result Execution time Memory
864194 2023-10-22T08:30:51 Z danikoynov Event Hopping (BOI22_events) C++14
30 / 100
 972 ms 29336 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 > 1000 || q > 100)
        {
            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 148 ms 15572 KB Output is correct
3 Correct 151 ms 15360 KB Output is correct
4 Correct 159 ms 15440 KB Output is correct
5 Incorrect 151 ms 15956 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 10 ms 25084 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 48 ms 25888 KB Output is correct
7 Correct 139 ms 26708 KB Output is correct
8 Correct 172 ms 27984 KB Output is correct
9 Correct 959 ms 29336 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 10 ms 25084 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 48 ms 25888 KB Output is correct
7 Correct 139 ms 26708 KB Output is correct
8 Correct 172 ms 27984 KB Output is correct
9 Correct 959 ms 29336 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 24920 KB Output is correct
13 Correct 10 ms 25132 KB Output is correct
14 Correct 13 ms 24924 KB Output is correct
15 Correct 47 ms 25892 KB Output is correct
16 Correct 139 ms 26692 KB Output is correct
17 Correct 168 ms 27732 KB Output is correct
18 Correct 972 ms 29088 KB Output is correct
19 Correct 133 ms 11908 KB Output is correct
20 Correct 125 ms 11792 KB Output is correct
21 Incorrect 147 ms 12112 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 10 ms 25084 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 48 ms 25888 KB Output is correct
7 Correct 139 ms 26708 KB Output is correct
8 Correct 172 ms 27984 KB Output is correct
9 Correct 959 ms 29336 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 24924 KB Output is correct
13 Correct 10 ms 24920 KB Output is correct
14 Correct 12 ms 24924 KB Output is correct
15 Correct 47 ms 25680 KB Output is correct
16 Correct 141 ms 26708 KB Output is correct
17 Correct 169 ms 27740 KB Output is correct
18 Correct 948 ms 29076 KB Output is correct
19 Correct 26 ms 14164 KB Output is correct
20 Correct 22 ms 13648 KB Output is correct
21 Incorrect 28 ms 14124 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 160 ms 15536 KB Output is correct
2 Correct 152 ms 15652 KB Output is correct
3 Correct 156 ms 15388 KB Output is correct
4 Correct 148 ms 15952 KB Output is correct
5 Correct 176 ms 16056 KB Output is correct
6 Correct 157 ms 15700 KB Output is correct
7 Correct 158 ms 15580 KB Output is correct
8 Correct 156 ms 15776 KB Output is correct
9 Correct 26 ms 14164 KB Output is correct
10 Correct 149 ms 15216 KB Output is correct
11 Correct 155 ms 15184 KB Output is correct
12 Correct 147 ms 15352 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 148 ms 15572 KB Output is correct
3 Correct 151 ms 15360 KB Output is correct
4 Correct 159 ms 15440 KB Output is correct
5 Incorrect 151 ms 15956 KB Output isn't correct
6 Halted 0 ms 0 KB -