1 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; #define x first #define y second #define pb push_back #define mp make_pair template <typename T> bool chkmin(T &x,T y){return y<x?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} template <typename T> void readint(T &x) { int f=1;char c;x=0; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c-'0'); x*=f; } const int MOD=998244353; inline int dmy(int x){return x>=MOD?x-MOD:x;} inline void inc(int &x,int y){x=dmy(x+y);} int qmi(int x,int y) { int ans=1; for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1)ans=1ll*ans*x%MOD; return ans; } const int MAXN=100005,MAXK=18; int n; int a[MAXN]; map<pii,int> mr; vector<int> G[MAXN]; int dfn[MAXN],dfn_cnt,anc[MAXN][MAXK],dep[MAXN]; int perm[MAXN],f[MAXN]; void dfs1(int u) { for(int j=1;j<MAXK;++j)anc[u][j]=anc[anc[u][j-1]][j-1]; dfn[u]=++dfn_cnt; for(auto v:G[u]) { if(v==anc[u][0])continue; anc[v][0]=u; dep[v]=dep[u]+1; dfs1(v); } } int lca(int u,int v) { if(dep[u]>dep[v])swap(u,v); for(int i=MAXK-1;i>=0;--i)if(dep[v]-dep[u]>=(1<<i))v=anc[v][i]; if(u==v)return u; for(int i=MAXK-1;i>=0;--i)if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i]; return anc[u][0]; } void dfs2(int u) { for(auto v:G[u]) { if(v==anc[u][0])continue; dfs2(v); f[u]+=f[v]; } } int main() { #ifdef LOCAL freopen("code.in","r",stdin); // freopen("code.out","w",stdout); #endif readint(n); for(int i=1;i<=n-2;++i) { int t[3]; for(int j=0;j<3;++j)readint(t[j]); readint(a[i]); sort(t,t+3); for(int j=0;j<3;++j) { pii p=mp(t[(j+1)%3],t[(j+2)%3]); if(p.x>p.y)swap(p.x,p.y); if(mr.count(p))G[mr[p]].pb(i),G[i].pb(mr[p]); else mr[p]=i; } perm[i]=i; } dfs1(1); sort(perm+1,perm+n-1,[&](int x,int y){return a[x]==a[y]?dfn[x]<dfn[y]:a[x]<a[y];}); for(int ii=2;ii<=n-2;++ii) { int x=perm[ii-1],y=perm[ii]; if(a[x]==a[y])++f[x],++f[y],f[lca(x,y)]-=2; } dfs2(1); int res=0; for(int i=2;i<=n-2;++i) if(!f[i])++res; printf("%d\n",res); return 0; }
- 1
信息
- ID
- 10550
- 时间
- 5000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者