Submission #2733338


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }


ll solve(int N,int M,vi& a,vi& b) {
    int mmax = N*(N-1)/2;
    if (M == mmax) {
        int best = 0xffffffff;
        for (int p=0; p<=N; ++p) {
            int q = N-p;
            int score = p*(p-1)/2 + q*(q-1)/2;
            best = min(best, score);
        }
        return best;
    }
    vvi d(N, vi(N, 0));
    rep(i,M){
        d[ a[i] ][ b[i] ] = d[ b[i] ][ a[i] ] = 1;
    }
    rep(i,N) d[i][i] = 1;

    vector<ii> non;
    repC2(i,j,N){
        if (d[i][j]) continue;
        non.pb(ii(i,j));
    }

    int x=non.back().first, y=non.back().second;
    non.pop_back();

    set<int> gx, gy;
    gx.insert(x); gy.insert(y);
#ifdef DEBUG
    // cerr << gx << gy << endl;
    // cerr << non << endl;
#endif
    for (ii p : non) {
        int u=p.first, v=p.second;
        if (d[u][x]==1 && d[v][y]==1) {
            //u
            for (int i: gx) if (!d[i][u]) return -1;
            for (int i: gy) if (!d[i][v]) return -1;
            gx.insert(u); gy.insert(v);
        } else if (d[u][y]==1 && d[v][x]==1) {
            for (int i: gy) if (!d[i][u]) return -1;
            for (int i: gx) if (!d[i][v]) return -1;
            gy.insert(u); gx.insert(v);
        } else {
            return -1;
        }
    }
    int Lx = gx.size(), Ly = gy.size(), rem = N-Lx-Ly;
    if (rem) {
        int half = N/2;
        if (Lx < half) {
            int up = min(half - Lx, rem);
            Lx += up;
            rem -= up;
        }
        if (Ly < half) {
            int up = min(half - Ly, rem);
            Ly += up;
            rem -= up;
        }
        if (rem) ++Lx;
    }
    return Lx*(Lx-1)/2 + Ly*(Ly-1)/2;
}

int main() {
    int N,M; cin >> N >> M;
    vi a(M), b(M);
    rep(i,M) {
        cin >> a[i] >> b[i];
        --a[i]; --b[i];
    }
    cout << solve(N,M,a,b) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Independence
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3181 Byte
Status
Exec Time 125 ms
Memory 4352 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt, sample4.txt
All 0 / 700 sample1.txt, sample2.txt, sample3.txt, sample4.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt
Case Name Status Exec Time Memory
1.txt 3 ms 384 KB
10.txt 3 ms 384 KB
11.txt 125 ms 4224 KB
12.txt 115 ms 4352 KB
13.txt 105 ms 4096 KB
14.txt 87 ms 4096 KB
15.txt 120 ms 4096 KB
16.txt 115 ms 3840 KB
17.txt 110 ms 3968 KB
18.txt 23 ms 1024 KB
19.txt 124 ms 4096 KB
2.txt 20 ms 1024 KB
20.txt 121 ms 4096 KB
21.txt 112 ms 3840 KB
22.txt 112 ms 3968 KB
23.txt 122 ms 2176 KB
24.txt 70 ms 1408 KB
25.txt 6 ms 4340 KB
26.txt 1 ms 256 KB
27.txt 1 ms 256 KB
28.txt 1 ms 256 KB
29.txt 1 ms 256 KB
3.txt 124 ms 4224 KB
4.txt 119 ms 4096 KB
5.txt 120 ms 3968 KB
6.txt 115 ms 4096 KB
7.txt 125 ms 4096 KB
8.txt 3 ms 384 KB
9.txt 20 ms 1024 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB
sample4.txt 1 ms 256 KB