2015年3月19日 星期四

2015/03/19 Codeforces 420C. Bug in Code

/*
    主要就是看
    滿足 提名A的人+提名B的人-提名A和B的人 >= P 的(A,B)數

    可以觀察到 對於大部分的 (A, B)
    提名A和B的人 等於0
    而 提名A的人+提名B的人 >= P 的(A,B)數
    可以用簡易的DP 求出
    接著再檢驗 那些 提名A和B的人 不等於0 (A, B)就好
*/
// http://codeforces.com/problemset/problem/420/C
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> pr;

pr mk(int a, int b)
{
    if( a > b ) swap(a, b);
    return pr(a, b);
}

int N, P;
int sup[400000] = {0};
int cnt[400000] = {0};
ll pre[400000] = {0};

map<pr, int> m;

int main()
{
    scanf("%d %d", &N, &P);

    for(int Ni = 0; Ni < N; Ni++)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        sup[a]++; sup[b]++;
        m[mk(a, b) ]++;
    }

    for(int Ni = 1; Ni <= N; Ni++)
        cnt[sup[Ni] ]++;

    for(int Ni = N; Ni >= 0; Ni--)
        pre[Ni] = pre[Ni+1]+cnt[Ni];

    ll Ans = 0;

    for(int Ni = 0; Ni <= N; Ni++)
    {
        ll Q = max(0, P-Ni);

        if( Q <= Ni ) Ans += (pre[Q]-1)*cnt[Ni];
        else Ans += pre[Q]*cnt[Ni];
    }

    Ans /= 2;

    for(auto x:m)
    {
        pr t = x.first;

        if( sup[t.first]+sup[t.second] >= P )
        {
            if( sup[t.first]+sup[t.second]-x.second < P ) Ans--;
        }
    }

    cout<<Ans<<endl;
}

沒有留言:

張貼留言