이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[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[a];
cc.push_front(rad);
while(b != rad)
cc.pb(b), b = tt[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;
}
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[nod])
continue;
if(!viz[vecin])
{
lvl[vecin] = lvl[nod] + 1;
viz[vecin] = 1;
tt[vecin] = nod;
d.pb(vecin);
}
else
if(lvl[nod] + lvl[vecin] + 1 >= 4 && 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;
}
컴파일 시 표준 에러 (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:54:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
# | 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... |