Submission #9493

#	Time	Username	Problem	Language	Result	Execution time	Memory
9493		mrcamel	Your life (kriii2_Y)	C++98	1 / 4	76 ms	6604 KiB

Y

#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 C[222222];
int res = -1;
int n, k;

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

    return M[idx];
}

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

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

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

    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);

        int cpx = C[px];
        int cx = C[x];

        if(cpx >= cx)
        {
            M[x] = M[py];
            C[py] = C[x]+1;
        }
    }

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

    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3