Submission #1103605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103605		12345678	Fire (BOI24_fire)	C++17	0 / 100	2052 ms	13736 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, m, nxt[nx], inv[nx], vs[nx], ans=-1, cnt;
pair<ll, ll> vl[nx];
vector<ll> d[nx];

bool dfs(int u)
{
    int in=0;
    vs[u]=1;
    for (auto v:d[u])
    {
        if (vs[v]==2) continue;
        if (vs[v]==1) return cnt++, vs[u]=vs[v]=2, 1;
        in=in||dfs(v);
    }
    if (vs[u]==2) return cnt++, 0;
    vs[u]=2;
    if (in) return cnt++, 1;
    return 0;
}

ll compare(int x, int y)
{
    pair<int, int> px=vl[x], py=vl[y];
    if (inv[x]) px.second+=m, py.first+=m, py.second+=m;
    if (inv[y]) py.second+=m;
    if (px.first<=py.first&&py.first<=px.second&&py.second>px.second) return py.second;
    return -1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>vl[i].first>>vl[i].second, inv[i]=vl[i].second<vl[i].first;
    for (int i=1; i<=n; i++)
    {
        pair<int, int> mx={-1, -1};
        for (int j=1; j<=n; j++) mx=max(mx, {compare(i, j), j});
        if (mx.first!=-1) d[mx.second].push_back(i);
        //cout<<"debug "<<i<<' '<<mx.second<<'\n';
    }
    for (int i=1; i<=n; i++) if (!vs[i]) cnt=0, dfs(i), ans=max(ans, cnt?cnt:-1);
    cout<<ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26