Submission #1147012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147012		Unforgettablepl	Logičari (COCI21_logicari)	C++20	0 / 110	0 ms	324 KiB

Main

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

#define int long long

const int modulo = 1e9+7;


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	for(int i=1;i<=n;i++){
		int a,b;
		cin >> a >> b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	auto solve = [&](int b1,int b2){
		vector<int> myLevel(n+1);
		vector<int> ans(4);
		vector<bool> allowed(4,true);
		function<void(int,int,int)> dfs = [&](int x,int p,int level){
			ans[level]++;
			myLevel[x]=level;
			int children = 0;
			for(int&i:adj[x])if(i!=p){
				if(i==b1 and x==b2)continue;
				if(i==b2 and x==b1)continue;
				children++;
				dfs(i,x,(level+1)&3);
			}
			if(children==0)allowed[(level+1)&3]=false;
		};
		dfs(1,0,0);
		allowed[2]=false;
		allowed[myLevel[b1]]=false;
		allowed[myLevel[b2]]=false;
		allowed[myLevel[(b1+3)&3]]=false;
		allowed[myLevel[(b2+3)&3]]=false;
		int anss = 1e9;
		for(int i=0;i<4;i++)if(allowed[i])anss=min(anss,ans[i]+ans[(i+1)&3]);
		return anss;
	};
	vector<bool> visited(n+1);
	vector<int> par(n+1);
	vector<pair<int,int>> edges;
	function<void(int,int)> dfs = [&](int x,int p){
		visited[x]=true;
		par[x]=p;
		for(int&i:adj[x])if(i!=p){
			if(visited[i]){
				if(!edges.empty())continue;
				edges.emplace_back(x,p);
				edges.emplace_back(par[p],p);
				edges.emplace_back(x,i);
				continue;
			}
			dfs(i,x);
		}
	};
	dfs(1,0);
	int anss = 1e9;
	for(auto&[a,b]:edges)anss=min(anss,solve(a,b));
	if(anss==1e9)cout<<"-1\n";
	else cout << anss << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50