oj.uz

Submission #9493

# Submission time Handle Problem Language Result Execution time Memory
9493 2014-09-28T06:50:28 Z mrcamel Your life (kriii2_Y) C++
1 / 4
 76 ms 6604 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 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3404 KB Output is correct
2 Correct 0 ms 3404 KB Output is correct
3 Correct 0 ms 3404 KB Output is correct
4 Correct 0 ms 3404 KB Output is correct
5 Correct 0 ms 3404 KB Output is correct
6 Correct 0 ms 3404 KB Output is correct
7 Correct 0 ms 3404 KB Output is correct
8 Correct 0 ms 3404 KB Output is correct
9 Correct 0 ms 3404 KB Output is correct
10 Correct 32 ms 5068 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3404 KB Output is correct
2 Correct 40 ms 5068 KB Output is correct
3 Correct 64 ms 6604 KB Output is correct
4 Correct 56 ms 6604 KB Output is correct
5 Correct 60 ms 6604 KB Output is correct
6 Correct 40 ms 5068 KB Output is correct
7 Correct 36 ms 5068 KB Output is correct
8 Incorrect 76 ms 6604 KB Output isn't correct
9 Halted 0 ms 0 KB -