Submission #53900

#	Time	Username	Problem	Language	Result	Execution time	Memory
53900		paulica	Potemkin cycle (CEOI15_indcyc)	C++14	80 / 100	80 ms	4076 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

#define fi first
#define se second
typedef pair<int, int> pii;

const int MaxN = 1010, MaxR = 1e5 + 10;
int n, r;

vector<pii> e[MaxN];
bool con[MaxN][MaxN];

pii edg[MaxR];
bool vis[MaxR], stk[MaxR];

int pre[MaxR];

void dfs(int x, int y, int id) {
    vis[id] = true;
    stk[id] = true;

    for (pii z : e[y]) {
        if (!con[x][z.fi] && z.fi != x) {
            if (!vis[z.se]) {
                pre[z.se] = id;
                dfs(y, z.fi, z.se);
            } else if (stk[z.se]) {
        //        for (int q = id; q != z.se; q = pre[q]) TRACE(q _ edg[q].fi _ edg[q].se);
          //      TRACE(z.se _ edg[z.se].fi _ edg[z.se].se);
            //    TRACE(x _ y);
 //               exit(0);
              //  cout << endl;
                vector<int> cyc = {x};
                for (int q = pre[id]; q != z.se; q = pre[q])
                    cyc.push_back(edg[q].fi + edg[q].se - cyc.back());
                cyc.push_back(y);
              //  for(int i : cyc) TRACE(i);
      //          exit(0);
                
                int m = cyc.size();
                //for (int i = 0; i < m; i++)
                  //  assert(!con[cyc[i]][cyc[(i + 2) % m]]);
/*
                int pos[MaxN];
                for (int i = 0; i < MaxN; i++) pos[i] = -1;
                for (int i = path.size() - 1; i >= 0; i--) {
                    if (pos[path[i]] != -1) {
                     //   TRACE(pos[path[i]] _ i);
//                        copy(path.begin() + pos[path[i]], path.begin() + i, cyc.begin());
                        //cyc = vector(path.begin() + pos[path[i]], path.begin() + i);
                        for (int j = pos[path[i]]; j > i; j--) cyc.push_back(path[j]);
                        break;
                    }
                    pos[path[i]] = i;
                }
                //for (int i : cyc) TRACE(i);
                //exit(0);
                for (int i = 0; i + 1 < cyc.size(); i++) 
                    assert(con[cyc[i]][cyc[i+1]]);
                assert(con[cyc[0]][cyc.back()]);
//                exit(0);

*/                
    //            int m = cyc.size();
                //for (int i = 0; i < cyc.size();i++) {
                  //  for(int j = (i + 2) % m; (j + 1) % m != i; j = (j + 1)% m)
                    //    assert(!con[cyc[i]][cyc[j]]);
                //}
  //              for (int i : cyc) cout << i << " "; cout << endl;
    //            for (int i = 0;i < m; i++) {
      //              for (int j = 0; j < m; j++) cout << con[cyc[i]][cyc[j]] << " ";
        //            cout << endl;
          //      }

                for (int len = 3; len < m; len++)
                    for (int i = 0; i < m; i++) {
                        if (con[cyc[i]][cyc[(i + len) % m]]) {
            //                TRACE(i _ (i + len) % m);
                            for (int j = (i + 1) % m; j != i; j = (j + 1) % m)
                                cout << cyc[j] << " ";
                            cout << cyc[i];

                            /*
                            vector<int> kurac;
                            for (int j = (i + 1) % m; j != i; j = (j + 1) % m)
                                kurac.push_back(cyc[j]);
                            kurac.push_back(cyc[i]);

                            m = kurac.size();
                            for (int ii = 0; ii < kurac.size();ii++) {
                              for(int jj = (ii + 2) % m; (jj + 1) % m != ii; jj = (jj + 1)% m)
                                assert(!con[kurac[ii]][kurac[jj]]);
                            }
*/

                            exit(0);                
                        }
                    }
  //                  */
            }
        }
    }

    stk[id] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> r;
    
    for (int i = 0; i < r; i++) {
        int x, y;
        cin >> x >> y;
        
        e[x].push_back({y, i});
        e[y].push_back({x, i});

        con[x][y] = con[y][x] = true;

        edg[i] = {x, y};
    }

    for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());

    for (int i = 0; i < r; i++) {
        if (!vis[i]) {
            dfs(edg[i].fi, edg[i].se, i);
        }
    }

    cout << "no";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10