Submission #582211

#	Time	Username	Problem	Language	Result	Execution time	Memory
582211		chirathnirodha	Logičari (COCI21_logicari)	C++17	110 / 110	194 ms	38468 KiB

Main

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
const ll inf=1e10;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
const int MAXN=100000;
vector<int> v[MAXN];
int parent[MAXN];
bool visited[MAXN];
vector<int> cyc;
vector<int> chil[MAXN];
ll dp[MAXN][2][2][2][2];
int rt,sp;

bool foundcy=false;
void dfs(int x){
	if(visited[x]){
		if(foundcy)return;
		foundcy=true;
		int cur=parent[x];
		cyc.PB(x);
		while(cur!=x){
			cyc.PB(cur);
			cur=parent[cur];
		}
		return;
	}
	visited[x]=true;
	for(int i=0;i<v[x].size();i++){
		if(parent[x]==v[x][i])continue;
		parent[v[x][i]]=x;
		dfs(v[x][i]);
	}
}


ll rec(int a,int b,int c,int x,int y){
	if(dp[a][b][c][x][y]!=-1)return dp[a][b][c][x][y];
	bool ok=true;
	if(a==rt && b!=x)ok=false;
	if(a==sp && b!=y)ok=false;
	if(a==sp && c && x)ok=false;
	if(!ok)return dp[a][b][c][x][y]=inf;

	int cov=0;
	if(c)cov++;
	if(a==rt && y)cov++;
	if(a==sp && x)cov++;

	ll tt=0;
	for(int i=0;i<chil[a].size();i++){
		tt+=rec(chil[a][i],0,b,x,y);
	}
	if(b)tt++;
	if(cov>0)dp[a][b][c][x][y]=min(inf,tt);
	else{
		ll best=inf;
		for(int i=0;i<chil[a].size();i++){
			ll temp=rec(chil[a][i],1,b,x,y)-rec(chil[a][i],0,b,x,y);
			best=min(best,temp);
		}
		dp[a][b][c][x][y]=min(best+tt,inf);
	}
	return dp[a][b][c][x][y];
}
void solve(){
    io();
	int n;cin>>n;
	for(int i=0;i<n;i++){
		int a,b;cin>>a>>b;a--;b--;
		v[a].PB(b);v[b].PB(a);
	}
	memset(parent,-1,sizeof(parent));
	parent[0]=0;
	dfs(0);
	rt=cyc[0];sp=cyc[1];
	queue<int> q;q.P(rt);
	memset(parent,-1,sizeof(parent));
	parent[rt]=rt;
	while(!q.empty()){
		int c=q.front();q.pop();
		for(int i=0;i<v[c].size();i++){
			int x=v[c][i];
			if(x==parent[c] || (x==rt && c==sp) || (x==sp && c==rt))continue;
			chil[c].PB(x);
			parent[x]=c;
			q.P(x);
		}
	}
	memset(dp,-1,sizeof(dp));
	ll ans=inf;
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			ll temp=rec(rt,i,0,i,j);
			ans=min(ans,temp);
		}
	}
	if(ans==inf)cout<<-1<<endl;
	else cout<<ans<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int)':
Main.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
Main.cpp: In function 'll rec(int, int, int, int, int)':
Main.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<chil[a].size();i++){
      |              ~^~~~~~~~~~~~~~~
Main.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i=0;i<chil[a].size();i++){
      |               ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:99:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i=0;i<v[c].size();i++){
      |               ~^~~~~~~~~~~~

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