SRM566 Div1 Easy(250)

TopCoder

PenguinSledding

道が交差する可能性が無いのは、

  • 道が0本の場合
  • 道が1本の場合
  • 全ての道があるチェックポイントに繋がっている場合
  • 3本の道が三角形になっている場合
#include <vector>
using namespace std;

class PenguinSledding{public:
long long countDesigns( int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2 )
{
    int n = numCheckpoints;
    vector<vector<bool> > E(n,vector<bool>(n));
    for ( int i=0; i<(int)checkpoint1.size(); i++ )
        E[checkpoint1[i]-1][checkpoint2[i]-1] = true,
        E[checkpoint2[i]-1][checkpoint1[i]-1] = true;

    long long ans = 0;

    //  道無し
    ans++;

    //  道が1本
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<i; j++ )
        if ( E[i][j] )
            ans++;

    //  道が星形
    for ( int i=0; i<n; i++ )
    {
        int c = 0;
        for ( int j=0; j<n; j++ )
            if ( j!=i && E[i][j] )
                c++;
        if ( c>=2 )
            ans += (1LL<<c) - c - 1;
    }

    //  道が3角形
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<i; j++ )
    for ( int k=0; k<j; k++ )
        if ( E[i][j] && E[j][k] && E[k][i] )
            ans++;
    
    return ans;
}};