Submission #208040

#	Time	Username	Problem	Language	Result	Execution time	Memory
208040		stefdasca	Potemkin cycle (CEOI15_indcyc)	C++14	50 / 100	1096 ms	2040 KiB

indcyc

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

bool is[1002][1002];
vector<int> v[1002];


int poz[1002], tt[12][1002], lvl[1002];
bool viz[1002];

bool tri(int rad, int a, int b)
{
  //  cout << rad << " " << a << " " << b << '\n';
    deque<int> cc;
    while(a != rad)
        cc.push_front(a), a = tt[0][a];
    cc.push_front(rad);
    while(b != rad)
        cc.pb(b), b = tt[0][b];
  //  for(int i = 0; i < cc.size(); ++i)
   //     cout << cc[i] << " ";
   // cout << '\n';
    for(int i = 0; i < cc.size(); ++i)
        for(int j = i+2; j < cc.size() - (i == 0); ++j)
            if(is[cc[i]][cc[j]])
                return 0;
    for(int i = 0; i < cc.size(); ++i)
        cout << cc[i] << " ";
    return 1;
}
int LCA(int a, int b)
{
    if(lvl[a] > lvl[b])
        swap(a, b);
    for(int i = 10; i >= 0; --i)
        if(tt[i][b] != 0 && lvl[b] - (1<<i) >= lvl[a])
            b = tt[i][b];
    for(int i = 10; i >= 0; --i)
        if(tt[i][a] != tt[i][b])
            a = tt[i][a], b = tt[i][b];
    return tt[0][a];
}
void bfs(int rad)
{
    deque<int> d;
    d.pb(rad);
    viz[rad] = 1;
    while(!d.empty())
    {
        int nod = d[0];
        d.pop_front();
        for(int i = 0; i < v[nod].size(); ++i)
        {
            int vecin = v[nod][i];
            if(vecin == tt[0][nod])
                continue;
            if(!viz[vecin])
            {
                lvl[vecin] = lvl[nod] + 1;
                viz[vecin] = 1;
                tt[0][vecin] = nod;
                for(int x = 1; x <= 10; ++x)
                    tt[x][vecin] = tt[x-1][tt[x-1][vecin]];
                d.pb(vecin);
            }
            else
                if(lvl[nod] + lvl[vecin] + 1 >= 4 && LCA(nod, vecin) == rad && tri(rad, nod, vecin))
                    exit(0);
        }
    }
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        is[a][b] = is[b][a] = 1;
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int root = 1; root <= n; ++root)
    {
        memset(lvl, 0, sizeof(lvl));
        memset(poz, 0, sizeof(poz));
        memset(tt, 0, sizeof(tt));
        memset(viz, 0, sizeof(viz));
        bfs(root);
    }
    cout << "no\n";
    return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'bool tri(int, int, int)':
indcyc.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cc.size(); ++i)
                    ~~^~~~~~~~~~~
indcyc.cpp:38:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = i+2; j < cc.size() - (i == 0); ++j)
                          ~~^~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cc.size(); ++i)
                    ~~^~~~~~~~~~~
indcyc.cpp: In function 'void bfs(int)':
indcyc.cpp:66:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[nod].size(); ++i)
                        ~~^~~~~~~~~~~~~~~

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