oj.uz

답안 #811006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
811006 2023-08-06T19:47:35 Z JakobZorz Potemkin cycle (CEOI15_indcyc) C++14
50 / 100
 1000 ms 8428 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=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second
 
int n,m;
unordered_set<int>nodes[1000];

void get_path(vector<int>& path,unordered_set<int>&path_set){
    int node=path.back();
    for(int next:nodes[node]){
        // check for repetitions and connections
        if(path_set.find(next)!=path_set.end())
            continue;
        
        bool rep=false;
        for(int i=1;i<(int)path.size()-1;i++){
            if(nodes[path[i]].find(next)!=nodes[path[i]].end()){
                rep=true;
                break;
            }
        }
        if(rep)
            continue;
        
        if(path.size()>=3&&nodes[next].find(path[0])!=nodes[next].end()){
            for(int i:path)
                cout<<i+1<<" ";
            cout<<next+1<<"\n";
            exit(0);
        }
        
        if(path.size()>=2&&nodes[path[0]].find(next)!=nodes[path[0]].end())
            continue;
        
        path.push_back(next);
        path_set.insert(next);
        get_path(path,path_set);
        path_set.erase(next);
        path.pop_back();
    }
}

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].insert(b);
        nodes[b].insert(a);
    }
    
    
    for(int i=0;i<n;i++){
        vector<int>path={i};
        unordered_set<int>path_set={i};
        get_path(path,path_set);
    }
    
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 89 ms 444 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1076 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 608 KB Output is correct
2 Execution timed out 1085 ms 596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1066 ms 4308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 2004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 8428 KB Output is correct
2 Execution timed out 1095 ms 8224 KB Time limit exceeded
3 Halted 0 ms 0 KB -