卧薪尝胆,厚积薄发。
GDSOI2018 谁是冠军
Date: Tue Aug 21 10:00:45 CST 2018 In Category: NoCategory

Description:

有 $n$ 个人,每个人有三个值,当有一个人有两个值都大于另一个人时可以获得胜利,问可能成为冠军的人。
$1\le n \le 100000$

Solution:

可以 $O(n^2)$ 枚举两个人连一条有向边,那么如果从一个人能到达其他所有人,那么它可能获得胜利,于是先用冒泡找出一个能赢得人,再用 $tarjan$ 缩点,那么和这个人在同一个强连通分量里的人就可以,但边数是 $O(n^2)$ 的,于是把三个指标两两组合,用主席树优化建图就行了。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
using namespace std;
int n;
#define MAXN 100010
struct people
{
int a,b,c;
int id;
int num;
}p[MAXN];
bool cmp_a(people x,people y){return x.a < y.a;}
bool cmp_b(people x,people y){return x.b < y.b;}
bool cmp_c(people x,people y){return x.c < y.c;}
#define MAXM 10000000
struct edge
{
int to,nxt;
}e[MAXM];
int edgenum = 0;
int lin[MAXM] = {0};
void addedge(int a,int b)
{
++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;
return;
}
struct node
{
int lc,rc;
}t[MAXM];
int ptr = 0;
int newnode(){return ++ptr;}
int root[4][MAXN];
#define mid ((l + r) >> 1)
void build(int &rt,int l,int r)
{
rt = newnode();
if(l == r)return;
build(t[rt].lc,l,mid);addedge(rt,t[rt].lc);
build(t[rt].rc,mid + 1,r);addedge(rt,t[rt].rc);
return;
}
void add(int rt,int k,int L,int R,int l,int r)
{
if(L > R)return;
if(L <= l && r <= R){addedge(k,rt);return;}
if(L <= mid)add(t[rt].lc,k,L,R,l,mid);
if(R > mid)add(t[rt].rc,k,L,R,mid + 1,r);
return;
}
void insert(int &rt,int k,int p,int l,int r)
{
int s = newnode();t[s] = t[rt];rt = s;
if(l == r){addedge(rt,k);return;}
if(p <= mid)insert(t[rt].lc,k,p,l,mid);
else insert(t[rt].rc,k,p,mid + 1,r);
addedge(rt,t[rt].lc);addedge(rt,t[rt].rc);
return;
}
int dfn[MAXM],low[MAXM],tot = 0;
stack<int> s;
bool v[MAXM];
int scc = 0,ins[MAXM];
int cur[MAXM],fa[MAXM];
int ans[MAXM],siz = 0;
void tarjan(int k)
{
int u = k;
while(true)
{
if(dfn[u] == 0)
{
dfn[u] = low[u] = ++tot;
s.push(u);v[u] = true;
cur[u] = lin[u];
}
bool flag = false;
for(int i = cur[u];i != 0;i = e[i].nxt)
{
cur[u] = i;
if(dfn[e[i].to] == 0)
{
cur[u] = e[i].nxt;
fa[e[i].to] = u;
u = e[i].to;
flag = true;
break;
}
else if(v[e[i].to])
{
low[u] = min(low[u],dfn[e[i].to]);
}
}
if(flag == false)
{
if(dfn[u] == low[u])
{
int t;
++scc;
siz = 0;
do
{
if(t <= n)ans[++siz] = t;
t = s.top();s.pop();
v[t] = false;ins[t] = scc;
}while(t != u);
}
if(u == k)break;
else
{
low[fa[u]] = min(low[fa[u]],low[u]);
u = fa[u];
}
}
}
return;
}
bool win(people x,people y)
{
int cnt = 0;
if(x.a > y.a)++cnt;
if(x.b > y.b)++cnt;
if(x.c > y.c)++cnt;
return (cnt >= 2);
}
int main()
{
freopen("champion.in","r",stdin);
// freopen("champion.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
p[i].id = i;
}
sort(p + 1,p + 1 + n,cmp_b);
for(int i = 1;i <= n;++i)p[i].num = i;
sort(p + 1,p + 1 + n,cmp_a);
ptr = n;
build(root[1][0],1,n);
for(int i = 1;i <= n;++i)
{
add(root[1][i - 1],p[i].id,1,p[i].num - 1,1,n);
root[1][i] = root[1][i - 1];
insert(root[1][i],p[i].id,p[i].num,1,n);
}
build(root[2][0],1,n);
sort(p + 1,p + 1 + n,cmp_c);
for(int i = 1;i <= n;++i)p[i].num = n;
sort(p + 1,p + 1 + n,cmp_a);
for(int i = 1;i <= n;++i)
{
add(root[2][i - 1],p[i].id,1,p[i].num - 1,1,n);
root[2][i] = root[2][i - 1];
insert(root[2][i],p[i].id,p[i].num,1,n);
}
build(root[3][0],1,n);
sort(p + 1,p + 1 + n,cmp_b);
for(int i = 1;i <= n;++i)
{
add(root[3][i - 1],p[i].id,1,p[i].num - 1,1,n);
root[3][i] = root[3][i - 1];
insert(root[3][i],p[i].id,p[i].num,1,n);
}
for(int i = 1;i <= ptr;++i)if(dfn[i] == 0)tarjan(i);
for(int i = 2;i <= n;++i)if(win(p[i - 1],p[i]))swap(p[i - 1],p[i]);
for(int i = 1;i <= n;++i)
if(ins[i] == ins[p[n].id])
printf("%d\n",i);
fclose(stdin);
fclose(stdout);
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡