[cf] *1700 D. Training Session 组合

前言

传送门 : 又是简单题型

思路

题目要求给出 n n n个二元关系 < a , b > 让你从中选取 3 3 3组使得没有 完全相同的 a o r b a or b aorb出现

根据 高中 的套路 : 正难则反 因此我们可以 : 求 任意选出的三组中 完全相同的

因此我们可以统计 每组 a 和 b a和b a和b出现的次数 因此对于当且组

仅有 ( m p x [ a [ i ] . x ] − 1 ) ∗ ( m p y [ a [ i ] . y ] − 1 ) (mpx[a[i].x] - 1) *(mpy[a[i].y]-1) (mpx[a[i].x]−1)∗(mpy[a[i].y]−1)种

所以我们只需要遍历一遍即可

CODE

#include 
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
#define unmp unordered_map
#define x first
#define y second
typedef pair PII;
const int N  = 2e5+10;
PII a[N];
unmp mpx,mpy;
void solve()
{
    mpx.clear(),mpy.clear();

    int n;cin>>n;
    ll ans = n*(n-1)*(n-2)/6;
    for(int i=1;i>a[i].x>>a[i].y;
        mpx[a[i].x]++,mpy[a[i].y]++;
    }

    for(int i=1;i