CFR 404 C. Restore Graph ( Adhoc )

Problem - 404C - Codeforces
The vertex i with dis[ i ] = 0 will be the origin, and if it doesn't exist, or multiple 0 distance vertices exist, there will be no solution. Otherwise iterate through all distances from smaller to larger and examine for each of those vertex[ i ], whether there exists a vertex j, such that dis[ j ] + 1 = dis[ i ] and degree[ j ] + 1 <= k.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = MAXN - 1;
typedef pair< int, int > pii;

int n, k;

struct V{
    int dis, id;
    V( int _d = -1, int _i = -1 ): dis(_d), id(_i){}
    bool operator < (const V &oth) const{
        return dis < oth.dis;
    }
} v[ MAXN ];

int deg[ MAXN ];
vector< pii > ans;

void solve(){
    sort( v, v + n );
    if( v[ 0 ].dis != 0 || v[ 1 ].dis == 0 ) return (void)puts("-1");
    vector< int > lst_id, cur_id;
    cur_id.push_back( 0 );
    for( int i = 1; i < n; ++i ){
        if( v[ i - 1 ].dis + 1 < v[ i ].dis ) return (void)puts("-1");
        if( v[ i - 1 ].dis < v[ i ].dis ){
            swap( lst_id, cur_id );
            cur_id.clear();
        }
        bool ok = false;
        for( int j = 0; j < lst_id.size(); ++j )
            if( deg[ lst_id[ j ] ] < k ){
                ans.push_back( pii( v[ i ].id, v[ lst_id[ j ] ].id ) );
                cur_id.push_back( i );
                ++deg[ i ];
                ++deg[ lst_id[ j ] ];
                ok = true;
                break;
            }
        if( !ok ) return (void)puts("-1");
    }
    printf("%d\n", (int)ans.size());
    for( int i = 0; i < ans.size(); ++i )
        printf("%d %d\n", ans[ i ].first, ans[ i ].second);
}

int main(){
    scanf("%d%d", &n, &k);
    for( int i = 0; i < n; ++i ){
        scanf("%d", &v[ i ].dis);
        v[ i ].id = i + 1;
    }
    solve();
    return 0;
}