题目传送门
题目大意
有$n$门科目有考试，第$i$门科目有两场考试，时间分别在$a_i, b_i\ \ (a_i < b_i)$，要求每门科目至少参加一场考试，不能在同一个时间参加两场考试，问最后参加的考试最早的时间是什么。
这几天，我怎么做的都是水题Emm....
考虑先将$a_i, b_i$离散化。
对于每一门考试，在$a_i, b_i$间连一条无向边。
对于每个连通块，讨论：
- 如果边数大于点数，显然无解
- 如果边数等于点数，那么答案必须大于等于点权中的最大值。
- 如果边数小于点数，那么最大不可用的时候会产生若干个基环树，所以答案必须大于等于点权中的次大值。
并查集随便维护一下就行了。
Code
/**
* Codeforces
* Problem#1027F
* Accepted
* Time: 873ms
* Memory: 63000k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
typedef bool boolean; template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} typedef class Input {
protected:
const static int limit = ;
FILE* file; int ss, st;
char buf[limit];
public: Input():file(NULL) { };
Input(FILE* file):file(file) { } void open(FILE *file) {
this->file = file;
} void open(const char* filename) {
file = fopen(filename, "r");
} char pick() {
if (ss == st)
st = fread(buf, , limit, file), ss = ;//, cerr << "str: " << buf << "ed " << st << endl;
return buf[ss++];
}
}Input; #define digit(_x) ((_x) >= '0' && (_x) <= '9') Input& operator >> (Input& in, unsigned& u) {
char x;
while (~(x = in.pick()) && !digit(x));
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
return in;
} Input& operator >> (Input& in, unsigned long long& u) {
char x;
while (~(x = in.pick()) && !digit(x));
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
return in;
} Input& operator >> (Input& in, int& u) {
char x;
while (~(x = in.pick()) && !digit(x) && x != '-');
int aflag = ((x == '-') ? (x = in.pick(), -) : ());
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
u *= aflag;
return in;
} Input& operator >> (Input& in, long long& u) {
char x;
while (~(x = in.pick()) && !digit(x) && x != '-');
int aflag = ((x == '-') ? (x = in.pick(), -) : ());
for (u = x - ''; ~(x = in.pick()) && digit(x); u = u * + x - '');
u *= aflag;
return in;
} Input in (stdin); #define pii pair<int, int> int n, m;
int *uf;
int *es;
int *mx, *smx;
pii* ps;
vector<int> br; int find(int x) {
return (uf[x] == x) ? (x) : (uf[x] = find(uf[x]));
} inline void init() {
in >> n;
ps = new pii[(n + )];
for (int i = ; i <= n; i++)
in >> ps[i].first >> ps[i].second;
} inline void descrete() {
for (int i = ; i <= n; i++) {
br.push_back(ps[i].first);
br.push_back(ps[i].second);
}
sort(br.begin(), br.end());
m = unique(br.begin(), br.end()) - br.begin();
for (int i = ; i <= n; i++) {
ps[i].first = lower_bound(br.begin(), br.begin() + m, ps[i].first) - br.begin();
ps[i].second = lower_bound(br.begin(), br.begin() + m, ps[i].second) - br.begin();
}
} void addEdge(int u, int v) {
if (find(u) != find(v)) {
u = find(u), v = find(v);
es[u] += es[v];
if (mx[u] < mx[v])
smx[u] = mx[u], mx[u] = mx[v];
else if (smx[u] < mx[v])
smx[u] = mx[v];
smx[u] = ((smx[u] > smx[v]) ? (smx[u]) : (smx[v]));
uf[v] = u;
}
es[find(u)]++;
} int res = -;
inline void solve() {
uf = new int[m];
es = new int[m];
mx = new int[m];
smx = new int[m]; for (int i = ; i < m; i++)
uf[i] = i, es[i] = -, mx[i] = i, smx[i] = -;
for (int i = ; i <= n; i++)
addEdge(ps[i].first, ps[i].second);
for (int i = ; i < m; i++)
if (find(i) == i) {
if (es[i] > ) {
res = -;
break;
}
if (!es[i])
res = max(res, mx[i]);
else
res = max(res, smx[i]);
} if (res == -)
puts("-1");
else
printf("%d\n", br[res]);
} int main() {
init();
descrete();
solve();
return ;
}