oj.uz

Submission #54405

# Submission time Handle Problem Language Result Execution time Memory
54405 2018-07-03T11:03:25 Z Costin Andrei Oncescu(#1303) Potemkin cycle (CEOI15_indcyc) C++11
100 / 100
 247 ms 3124 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, d[1009], side[1009], how[1009], x[100009], y[100009];
bool ap[1009][1009];
vector < int > v[1009];
queue < int > cc;

void finish (int x, int frm, int to)
{
    for (int i=1; i<=N; i++)
        d[i] = -1, side[i] = (i == x || ap[i][x]);
    d[x] = 0, d[frm] = 0, side[to] = 0;
    cc.push (frm), d[frm] = 0, how[frm] = 0;
    while (!cc.empty ())
    {
        int nod = cc.front ();
        cc.pop ();
        for (auto it : v[nod])
            if (d[it] == -1 && side[it] == 0)
                d[it] = d[nod] + 1, how[it] = nod, cc.push (it);
    }
    while (to)
        printf ("%d ", to),
        to = how[to];
    printf ("%d\n", x);
}

void searchPair (int x, vector < int > &d1)
{
    int frm = -1, to = -1;
    for (int i=0; i<d1.size (); i++)
        for (int j=i + 1; j<d1.size (); j++)
            if (ap[d1[i]][d1[j]] == 0)
            {
                frm = d1[i], to = d1[j];
                i = d1.size ();
                break;
            }
    if (to != -1)
    {
        finish (x, frm, to);
        exit (0);
    }
}

bool covered[1009], coveredD1[1009];
vector < int > d1;
void dfs (int nod)
{
    covered[nod] = 1;
    for (auto it : v[nod])
        if (side[it] == 0 && covered[it] == 0) dfs (it);
        else
        if (side[it] == 1 && coveredD1[it] == 0)
            coveredD1[it] = 1, d1.push_back (it);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=M; i++)
{
    scanf ("%d %d", &x[i], &y[i]);
    v[x[i]].push_back (y[i]);
    v[y[i]].push_back (x[i]);
    ap[x[i]][y[i]] = ap[y[i]][x[i]] = 1;
}
for (int x=1; x<=N; x++)
{
    for (int i=1; i<=N; i++)
        side[i] = (x == i || ap[i][x]);
    for (int i=1; i<=N; i++)
        covered[i] = 0;
    coveredD1[x] = 1;
    for (int i=1; i<=N; i++)
        if (side[i] == 0 && covered[i] == 0)
        {
            d1.clear ();
            dfs (i);
            for (auto it : d1)
                coveredD1[it] = 0;
            searchPair (x, d1);
        }
    coveredD1[x] = 0;
}
printf ("no\n");
return 0;
}

Compilation message

indcyc.cpp: In function 'void searchPair(int, std::vector<int>&)':
indcyc.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<d1.size (); i++)
                   ~^~~~~~~~~~~
indcyc.cpp:34:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=i + 1; j<d1.size (); j++)
                           ~^~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:68:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x[i], &y[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 744 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1020 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct
3 Correct 4 ms 1020 KB Output is correct
4 Correct 11 ms 1020 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1020 KB Output is correct
2 Correct 11 ms 1032 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2572 KB Output is correct
2 Correct 9 ms 2572 KB Output is correct
3 Correct 215 ms 2608 KB Output is correct
4 Correct 109 ms 2608 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2608 KB Output is correct
2 Correct 168 ms 2608 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2996 KB Output is correct
2 Correct 24 ms 2996 KB Output is correct
3 Correct 25 ms 3000 KB Output is correct
4 Correct 247 ms 3124 KB Output is correct