CSES - HIIT Open 2019 - Results
Submission details
Task:Many Cycles
Sender:O(n^10)
Submission time:2019-05-25 13:00:19 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.04 sdetails
#2ACCEPTED0.02 sdetails

Compiler report

input/code.cpp: In function 'bool dfs(int, int)':
input/code.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
int t;
vector<int> adj[102];
int vis[103], cycles[103];
int vid = 1;
int arr[104][104];
int par[104];
bool dfs(int x, int p) {
vis[x] = vid;
//cout<<x<<" "<<p<<"\n";
for (int i = 0; i < adj[x].size(); i++) {
int u = adj[x][i];
if (u == p) continue;
if (arr[x][u] == vid) continue;
if (vis[u] == vid) {
//cout<<x<<" on syklissä ja "<<u<<" on syklissä\n";
int kk = x;
while (kk != u) {
cycles[kk]++;
//cout<<"cycles["<<kk<<"] ++ = "<<cycles[kk]<<"\n";
if (cycles[kk] > 1) return true;
kk = par[kk];
}
cycles[u]++;
if (cycles[u] > 1) return true;
arr[x][u] = vid;
arr[u][x] = vid;
//cout<<x<<" on syklissä ja "<<u<<" on syklissä\n";
continue;
}
vis[u] = vid;
par[u] = x;
if (dfs(u, x)) return true;
}
return false;
}
bool solve(int n, int m) {
for (int i = 0; i < m; i++) {
int a,b; cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vid++;
par[1] = 1;
return dfs(1, 1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>t;
for (int j = 0; j < t; j++) {
int n, m; cin>>n>>m;
for (int i = 1; i <= 100; i++) adj[i].clear(), cycles[i] = 0, par[i] = 0;
bool res = solve(n, m);
if (res) cout<<"YES\n";
else cout<<"NO\n";
}
}

Test details

Test 1

Verdict:

input
1000
100 78
97 68
75 90
58 80
...

correct output
YES
YES
YES
YES
NO
...

user output
YES
NO
NO
NO
NO
...
Truncated

Test 2

Verdict: ACCEPTED

input
11
2 1
1 2
6 6
1 2
...

correct output
NO
NO
NO
YES
YES
...

user output
NO
NO
NO
YES
YES
...