# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
171225 | Ruxandra985 | Potemkin cycle (CEOI15_indcyc) | C++14 | 985 ms | 6112 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |