oj.uz

Submission #171225

# Submission time Handle Problem Language Result Execution time Memory
171225 2019-12-27T20:08:36 Z Ruxandra985 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 985 ms 6112 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize "Ofast"
#define DIMN 1010

using namespace std;
vector <int> v[DIMN];
int tt[DIMN] , f[DIMN] , sol[DIMN] , ad[DIMN][DIMN] , ok[DIMN][DIMN];
pair <int,int> mch[100010];
int dont[100010];
int elem , found , n , m;
deque <int> dq;
char buff[2000000];
int poz = 0;
int getnr(){
    int nr = 0;

    while ('0' > buff[poz] || buff[poz] > '9')
        poz++;
    while ('0' <= buff[poz] && buff[poz] <= '9'){
        nr = nr * 10 + buff[poz] - '0';
        poz++;
    }
    return nr;
}
void ignoree (int x){
    int i , nod , vecin , sts = 0;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    memset (f , 0 , sizeof(f));
    tt[mch[x].first] = 0;
    for (i=0;i<v[mch[x].second].size();++i){
        vecin = v[mch[x].second][i];
        if (ad[mch[x].first][vecin] && ad[mch[x].second][vecin])
            sts++;
    }
    //printf ("%d %d\n",sts , v[mch[x].second].size());
    if (sts == v[mch[x].second].size())
        return;

    dq.clear();
    dq.push_back(mch[x].first);
    f[mch[x].first] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();
        for (i=0;i<v[nod].size();++i){
            vecin = v[nod][i];
            if (vecin == mch[x].second && nod != mch[x].first){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                found = 1;
                break;
            }
            if (ad[mch[x].first][vecin] && ad[mch[x].second][vecin]){
                if (vecin != mch[x].second)
                    f[vecin] = 2;
            }
            else if (!f[vecin]){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                dq.push_back(vecin);
            }
        }
    }
    if (found){
        nod = mch[x].second;
        while (nod){
            sol[++elem] = nod;
            nod = tt[nod];
        }
    }
}
void ignore_node (int x){
    int i , nod , vecin , sts = 0 , j , vecin1 , vecin2 , sf;
    /// cel mai scurt drum de la mch[x].first la mch[x].second
    if (found)
        return;
    memset (f , 0 , sizeof(f));
    tt[x] = 0;
    for (i=0;i<v[x].size();++i){
        for (j=i+1;j<v[x].size();j++){
            vecin1 = v[x][i];
            vecin2 = v[x][j];
            if (ad[vecin1][vecin2]){
                dont[ad[x][vecin1]] = x;
                dont[ad[x][vecin2]] = x;
                dont[ad[vecin2][vecin1]] = x;
            }
        }
    }
    //printf ("%d %d\n",sts , v[mch[x].second].size());

    dq.clear();
    dq.push_back(x);
    f[x] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();
        if (found)
            break;
        for (i=0;i<v[nod].size();++i){
            vecin = v[nod][i];
            if (dont[ad[nod][vecin]] == x){
                if (vecin == x){
                    found = 1;
                    //f[vecin] = 1 + f[nod];
                    //tt[vecin] = nod;
                    sf = nod;
                    break;
                }
            }
            else if (!f[vecin]){
                f[vecin] = 1 + f[nod];
                tt[vecin] = nod;
                dq.push_back(vecin);
            }

        }
    }
    if (found){
        nod = sf;
        while (nod){
            sol[++elem] = nod;
            nod = tt[nod];
        }
    }
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , vecin1 , vecin2;
    fread (buff , 1 , 2000000 , fin);
    n = getnr();
    m = getnr();
    for (i=1;i<=m;++i){
        mch[i].first = getnr();
        mch[i].second = getnr();
        v[mch[i].first].push_back(mch[i].second);
        v[mch[i].second].push_back(mch[i].first);
        ad[mch[i].first][mch[i].second] = i;
        ad[mch[i].second][mch[i].first] = i;
        ad[mch[i].second][mch[i].second] = 1;
        ad[mch[i].first][mch[i].first] = 1;
    }
    int ok = 0 , mom;
    for (int x=1;x<=n;x++){
        mom = 1;
        for (i=0;i<v[x].size();++i){
            for (int j=i+1;j<v[x].size();j++){
                vecin1 = v[x][i];
                vecin2 = v[x][j];
                if (ad[vecin1][vecin2]){
                    mom = 0;
                }
            }
        }
        ok = (ok + mom);

    }
    if (ok == 1 && n > 300){
        for (i=1;i<=n;i++){
            //printf ("%d ",i);
            ignore_node(i);
            if (found)
                break;
        }
    }
    else {
        for (i=1;i<=m;++i){
            /// daca ignoram muchia i
            ignoree (i);
            if (found)
                break;
        }
    }

    if (!found)
        fprintf (fout,"no");
    else {
        for (i=1;i<=elem;++i)
            fprintf (fout,"%d ",sol[i]);
    }
    return 0;

}

Compilation message

indcyc.cpp: In function 'void ignoree(int)':
indcyc.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[mch[x].second].size();++i){
              ~^~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:36:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (sts == v[mch[x].second].size())
         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
indcyc.cpp: In function 'void ignore_node(int)':
indcyc.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[x].size();++i){
              ~^~~~~~~~~~~~
indcyc.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=i+1;j<v[x].size();j++){
                    ~^~~~~~~~~~~~
indcyc.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();++i){
                  ~^~~~~~~~~~~~~~
indcyc.cpp:73:27: warning: unused variable 'sts' [-Wunused-variable]
     int i , nod , vecin , sts = 0 , j , vecin1 , vecin2 , sf;
                           ^~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:148:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[x].size();++i){
                  ~^~~~~~~~~~~~
indcyc.cpp:149:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=i+1;j<v[x].size();j++){
                            ~^~~~~~~~~~~~
indcyc.cpp:132:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff , 1 , 2000000 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1688 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct
3 Correct 4 ms 1656 KB Output is correct
4 Correct 12 ms 1784 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1656 KB Output is correct
2 Correct 35 ms 1656 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5748 KB Output is correct
2 Correct 20 ms 5068 KB Output is correct
3 Correct 125 ms 5752 KB Output is correct
4 Correct 28 ms 4984 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4952 KB Output is correct
2 Correct 985 ms 4956 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4600 KB Output is correct
2 Correct 137 ms 4700 KB Output is correct
3 Correct 46 ms 6008 KB Output is correct
4 Correct 267 ms 6112 KB Output is correct