제출 #1147060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147060		Unforgettablepl	Logičari (COCI21_logicari)	C++20	60 / 110	57 ms	22344 KiB

Main

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

#define int long long

const int modulo = 1e9+7;
const int INF = 5e12;

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){
		function<array<int,4>(int,int)> dfs = [&](int x,int p){
			array<int,4> DP = {0,0,1,1};
			int minima = INF;
			int minima2 = INF;
			for(int&i:adj[x])if(i!=p){
				if(i==b1 and x==b2)continue;
				if(i==b2 and x==b1)continue;
				auto res = dfs(i,x);
				DP[0]+=res[1];
				DP[1]+=res[1];
				DP[2]+=res[0];
				DP[3]+=res[0];
				minima=min(minima,res[2]-res[1]);
				minima2=min(minima2,res[3]-res[0]);
			}
			DP[1]+=minima;
			DP[2]+=minima2;
			if(x==b1 or x==b2)DP[2]=DP[3]=INF;
			return DP;
		};
		auto ansss = dfs(1,0);
		return min(ansss[1],ansss[2]);
	};
	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 = INF;
	for(auto&[a,b]:edges)anss=min(anss,solve(a,b));
	if(anss>n)cout<<"-1\n";
	else cout << anss << '\n';
}

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