oj.uz

Submission #810993

# Submission time Handle Problem Language Result Execution time Memory
810993 2023-08-06T19:13:01 Z JakobZorz Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 876 ms 2140 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e6+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second
 
int n,m;
vector<int>nodes[1000];
bool taken1[1000];
bool taken2[1000];

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    
    for(int n1=0;n1<n;n1++){
        for(int ne:nodes[n1])
            taken1[ne]=true;
        
        for(int n2:nodes[n1]){
            for(int ne:nodes[n2])
                taken2[ne]=true;
            
            for(int n3:nodes[n2]){
                if(taken1[n3]||n3==n1)
                    continue;
                
                for(int n4:nodes[n3]){
                    if(taken1[n4]&&!taken2[n4]&&n4!=n2){
                        cout<<n1+1<<" "<<n2+1<<" "<<n3+1<<" "<<n4+1<<"\n";
                        return 0;
                    }
                }
            }
            
            for(int ne:nodes[n2])
                taken2[ne]=false;
        }
        
        for(int ne:nodes[n1])
            taken1[ne]=false;
    }
    
    cout<<"no\n";
    return 0;
}

/*
 
5 6
1 2
1 3
2 3
4 3
5 2
4 5
 
4 5
1 2
2 3
3 4
4 1
1 3
 
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 352 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 360 KB Output is correct
2 Incorrect 3 ms 340 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 408 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 399 ms 1260 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 876 ms 760 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 2140 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -