Codeforces 1027F. Session in BSU

思路：

对第一门考试，使用前一个时间，做标记，表示该时间已经用过，并让第一个时间指向第二个时间，表示，若之后的考试时间和当前第一个时间冲突时，可以找到当前第二个时间来代替

对每一门考试，如果前一个时间没有被使用过，直接用前一个时间，否则看前一个时间和后一个时间分别可以指向哪一个时间，假设指向x，y，看x和y的状态和大小，如果x，y都已经使用过，表示无解，否则的话，选择较小的，并更新时间指向的状态

时间的指向状态更新需要用 map离散数据并用并查集维护

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<string.h>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<fstream>

#include<cstdlib>

#include<ctime>

#include<list>

#include<climits>

#include<bitset>

using namespace std;

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("input.in", "r", stdin);freopen("output.in", "w", stdout);

#define left asfdasdasdfasdfsdfasfsdfasfdas1

#define tan asfdasdasdfasdfasfdfasfsdfasfdas

typedef long long ll;

typedef unsigned int un;

const int desll[][]={{,},{,-},{,},{-,}};

const ll mod=1e9+;

const int maxn=2e6+;

const int maxm=1e6+;

const double eps=1e-;

int m,n;

int ar[maxn];

pair<int,int> pa[maxn];

map<int,int> ma;

bool wa[maxn];

int f[maxn];

int fin(int x)

{

    return f[x]==x?x:f[x]=fin(f[x]);

}

int main()

{

    scanf("%d",&n);

    m=;

    for(int i=;i<n;i++)scanf("%d%d",&pa[i].first,&pa[i].second),

        ar[m++]=pa[i].first,ar[m++]=pa[i].second;

    sort(ar,ar+m);

    m=unique(ar,ar+m)-ar;

    for(int i=;i<m;i++){

        ma[ar[i]]=i;

    }

    for(int i=;i<m;i++)f[i]=i;

    memset(wa,,sizeof(wa));int ans=;

    for(int i=;i<n;i++){

        int a=pa[i].first,b=pa[i].second;

        if(!wa[ma[a]]){

            wa[ma[a]]=;

            ans=max(ans,a);

            f[ma[a]]=ma[b];

            continue;

        }

        int x=fin(ma[a]);

        int y=fin(ma[b]);//分别寻找a，b指向的时间

        if(wa[x] && wa[y]){

            printf("-1\n");

            return ;

        }

        if(wa[x]==false && wa[y]==false){

            if(ar[x]<ar[y]){

                f[x]=y;//更新时间指向的状态

                wa[x]=;

                ans=max(ans, ar[x]);

            }

            else{

                f[y]=x;//更新时间指向的状态

                wa[y]=;

                ans=max(ans, ar[y]);

            }

        }

        else if(!wa[x]){

            wa[x]=;

            ans=max(ans, ar[x]);

        }

        else{

            wa[y]=;

            ans=max(ans, ar[y]);

        }

        f[ma[a]]=y;//更新时间指向的状态

    }

    printf("%d\n",ans);

    return ;

}

秒客网

Codeforces 1027F. Session in BSU

相关文章