oj.uz

Submission #864197

# Submission time Handle Problem Language Result Execution time Memory
864197 2023-10-22T08:32:53 Z danikoynov Event Hopping (BOI22_events) C++14
30 / 100
 956 ms 33236 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();
            if (n > 1000 || q > 100)
                exit(0);
            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 6488 KB Output is correct
2 Correct 148 ms 16384 KB Output is correct
3 Correct 152 ms 16216 KB Output is correct
4 Correct 158 ms 16224 KB Output is correct
5 Incorrect 148 ms 16824 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 6488 KB Output is correct
3 Correct 13 ms 25084 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 13 ms 24924 KB Output is correct
6 Correct 47 ms 25684 KB Output is correct
7 Correct 139 ms 26704 KB Output is correct
8 Correct 174 ms 27728 KB Output is correct
9 Correct 951 ms 29332 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 6488 KB Output is correct
3 Correct 13 ms 25084 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 13 ms 24924 KB Output is correct
6 Correct 47 ms 25684 KB Output is correct
7 Correct 139 ms 26704 KB Output is correct
8 Correct 174 ms 27728 KB Output is correct
9 Correct 951 ms 29332 KB Output is correct
10 Correct 1 ms 6492 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 13 ms 25080 KB Output is correct
15 Correct 47 ms 25876 KB Output is correct
16 Correct 141 ms 26704 KB Output is correct
17 Correct 168 ms 27752 KB Output is correct
18 Correct 945 ms 29268 KB Output is correct
19 Incorrect 147 ms 33236 KB Output isn't correct
20 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 6488 KB Output is correct
3 Correct 13 ms 25084 KB Output is correct
4 Correct 10 ms 24924 KB Output is correct
5 Correct 13 ms 24924 KB Output is correct
6 Correct 47 ms 25684 KB Output is correct
7 Correct 139 ms 26704 KB Output is correct
8 Correct 174 ms 27728 KB Output is correct
9 Correct 951 ms 29332 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 12 ms 25108 KB Output is correct
13 Correct 10 ms 24924 KB Output is correct
14 Correct 14 ms 24924 KB Output is correct
15 Correct 48 ms 25684 KB Output is correct
16 Correct 143 ms 26692 KB Output is correct
17 Correct 185 ms 27764 KB Output is correct
18 Correct 956 ms 29080 KB Output is correct
19 Correct 26 ms 14672 KB Output is correct
20 Correct 26 ms 13936 KB Output is correct
21 Incorrect 28 ms 14676 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 149 ms 16208 KB Output is correct
2 Correct 148 ms 16624 KB Output is correct
3 Correct 161 ms 16192 KB Output is correct
4 Correct 148 ms 16720 KB Output is correct
5 Correct 153 ms 16724 KB Output is correct
6 Correct 178 ms 16444 KB Output is correct
7 Correct 155 ms 16360 KB Output is correct
8 Correct 152 ms 16436 KB Output is correct
9 Correct 26 ms 14672 KB Output is correct
10 Correct 149 ms 15956 KB Output is correct
11 Correct 145 ms 15952 KB Output is correct
12 Correct 148 ms 16068 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 148 ms 16384 KB Output is correct
3 Correct 152 ms 16216 KB Output is correct
4 Correct 158 ms 16224 KB Output is correct
5 Incorrect 148 ms 16824 KB Output isn't correct
6 Halted 0 ms 0 KB -