oj.uz

답안 #864170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864170 2023-10-22T07:55:58 Z danikoynov Event Hopping (BOI22_events) C++14
20 / 100
 179 ms 19792 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[maxn];
     
    int used[maxn], dist[5010][5010];
    int my_queue[maxn];
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 2 ms 12636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 16336 KB Output is correct
2 Correct 165 ms 16464 KB Output is correct
3 Correct 166 ms 16716 KB Output is correct
4 Correct 151 ms 17024 KB Output is correct
5 Correct 153 ms 16772 KB Output is correct
6 Correct 179 ms 16840 KB Output is correct
7 Correct 158 ms 19536 KB Output is correct
8 Correct 159 ms 19792 KB Output is correct
9 Correct 27 ms 17692 KB Output is correct
10 Correct 152 ms 19196 KB Output is correct
11 Correct 148 ms 19028 KB Output is correct
12 Correct 150 ms 19196 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -