oj.uz

Submission #9400

# Submission time Handle Problem Language Result Execution time Memory
9400 2014-09-28T06:10:00 Z mrcamel Your life (kriii2_Y) C++
0 / 4
 0 ms 2536 KB 
#include <cstdio>
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

#define in cin
#define out cout
#define PII pair<int, int>
#define x first
#define y second
#define pi 3.14159265358979323846
#define REP(i, v) for(int i=0; i<v; i++)
#define REPEQ(i, s, e) for(int i=s; i<=e; i++)
#define REPRV(i, s, e) for(int i=s; i>=e; i--)
#define all(v) v.begin(), v.end()
#define long long int int64
#define BIG(a, b) ( (a>b?a:b) )

int M[222222];
int res = -1;
int n, k;

int f(int idx)
{
    if( idx != M[idx] )
    {
        M[idx] = f( M[idx] );
    }

    return M[idx];
}

int f2(int idx, int c)
{
    if( idx != M[idx] )
    {
        f2( M[idx], c+1);
    }
    else if( idx == n)
    {
        res = c;
    }

    return 0;
}

int main()
{
    //freopen("in.txt", "r+", stdin);
    ios::sync_with_stdio(false);

    in >> n >> k;
    REPEQ(i, 1, n)
    {
        M[i] = i;
    }

    vector<PII> v;
    REP(i, k)
    {
        int x, y; in >> x >> y;
        v.push_back( make_pair(x, y) );
    } sort( all(v) );

    REP(i, k)
    {
        int x = v[i].x;
        int y = v[i].y;

        int px = f(x);
        int py = f(y);

        M[px] = M[py];
    }

    f2(1, 0);
    out << res-1 << endl;

    return 0;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -