Submission #1257977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257977		_rain_	Potemkin cycle (CEOI15_indcyc)	C++20	70 / 100	58 ms	1096 KiB

indcyc

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>(x))&(1))

template<class X,class Y>
	bool maximize(X &x,Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x > y) return x = y , true; else return false;
	}

const int N = (int) 1e3;
const int MAXR = (int)1e5;
	vector<int>ke[N + 2];
	
		void add_canh(int u , int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
		
	int n , m;
	int u[MAXR + 2] , v[MAXR + 2];
		
namespace subtask1{
	bool check(void){
		return n <= 10;
	}
	
	bitset<11>adj[N + 2];
	void main_code(){
		vector<int>vert;
		for(int i = 1; i <= m; ++i) {
			adj[u[i]][v[i]] = true;
			adj[v[i]][u[i]] = true;
		}
		for(int i = 1; i <= n; ++i) vert.push_back(i);
		int t = 1;
		int mx = 0;
		do{
			bitset<11>t;
			int sz = 1;
			for(int i = 1; i < vert.size(); ++i){
				bitset<11>tt ;
				tt[vert[i-1]] = true;
				if (i > 1 && (t & adj[vert[i]])!=tt) break;
				if (i == 1 && adj[vert[i]][vert[i-1]]==false) break;
				if (i - 1 != 0 && adj[vert[i]][vert[0]]) {
					sz = i + 1;
					break;
				}
				
				t[vert[i]] = true;
			}
			if (sz >= 4){
				for(int j = 0; j < sz; ++j) cout << vert[j] << ' ';
				return ;
			}
		} while (next_permutation(vert.begin() , vert.end()));
		cout<<"no";
	}
}

namespace subtask2{
	bool check(){
		return n <= 300;
	}
	
	int trace[N + 2] = {};
	int dist[N + 2] = {};
	bool open[N + 2] = {};
	
	void bfs(int source){
		for(int i = 1; i <= n; ++i) trace[i] = -1 , dist[i] = 0;
		queue<int>q;
		q.push(source);
		trace[source] = 0 ,dist[source] = 1;
		while (q.size()){
			int u = q.front(); q.pop();
			
			for(auto& v : ke[u]){
				if (open[v] && trace[v] == -1){
					trace[v] = u;
					dist[v] = dist[u] + 1;
					q.push(v);
				}
				else if (open[v]==false && trace[v] == -1){
					trace[v] = u;
					dist[v] = dist[u] + 1;
				}
			}
		}
		return;
	}
	void trace_road(int source , int sink){
		vector<int>road;
//		road.push_back(source);
		while (sink){
			road.push_back(sink);
			sink = trace[sink];
		}
		for(auto& x : road) cout << x << ' ';
	}
	
	void main_code(){
		for(int i = 1; i <= m; ++i){
			add_canh(u[i] , v[i]);
		}
		for(int i = 1; i <= n; ++i) open[i] = true;
		for(int root = 1; root <= n; ++root){
			open[root] = false;
			for(auto& v : ke[root]) open[v] = false;
			for(auto& v1 : ke[root]){
				open[v1] = true;
				bfs(v1);
				for(auto& v2 : ke[root]){
					if (dist[v2] >= 3){
						trace_road(v1,v2);
						cout<<root;
						return ;
					}
				}
				open[v1] = false;
			}
			open[root] = true;
			for(auto& v : ke[root]) open[v] = true;
		}
		cout << "no";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r")){
		freopen(name".inp","r",stdin);
		freopen(name".out","w",stdout);
	}
	
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		cin >> u[i] >> v[i];
	}
//	if (subtask1::check()) return subtask1::main_code() , 0;
	if (subtask2::check()) return subtask2::main_code() , 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:142:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |                 freopen(name".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
indcyc.cpp:143:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |                 freopen(name".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10