제출 #864195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864195		danikoynov	Event Hopping (BOI22_events)	C++14	30 / 100	1561 ms	44744 KiB

events

    #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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30