Submission #895985

#	Time	Username	Problem	Language	Result	Execution time	Memory
895985		pcc	Love Polygon (BOI18_polygon)	C++14	100 / 100	117 ms	24920 KiB

polygon

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;
vector<string> all;
pair<string,string> tmp[mxn];
int n;
int arr[mxn];
vector<int> jelly[mxn];
bitset<mxn> vis,psyco;
int dp[mxn][2];
int deg[mxn];
queue<int> q;
int ans;

void dfs(int now){
	dp[now][0] = dp[now][1] = 0;
	int sh = 1e9;
	for(auto nxt:jelly[now]){
		if(psyco[nxt])continue;
		dfs(nxt);
		dp[now][0] += max(dp[nxt][0],dp[nxt][1]);
		sh = min(sh,max(dp[nxt][0],dp[nxt][1])-dp[nxt][0]);
	}
	dp[now][1] = max(dp[now][0],dp[now][0]-sh+1);
	return;
}

void calc(vector<pii> &v){
	if(v.size() == 1){
		ans -= max(v[0].fs,v[0].sc);
		return;
	}
	else if(v.size() == 2){
		int tmp = max(v[0].fs+v[1].fs+2,max(v[0].fs,v[0].sc)+max(v[1].fs,v[1].sc));
		ans -= tmp;
		return;
	}
	int re = 0;
	int dp[v.size()][2] = {};
	dp[0][1] = max(v[0].fs,v[0].sc);
	dp[0][0] = v[0].fs;
	for(int i = 1;i<v.size();i++){
		dp[i][0] = dp[i-1][1]+v[i].fs;
		dp[i][1] = max({dp[i-1][0]+v[i].fs+1,dp[i-1][1]+v[i].sc,dp[i][0]});
	}
	re = max(re,dp[v.size()-1][1]);
	v.push_back(v[0]);
	v.erase(v.begin());
	memset(dp,0,sizeof(dp));
	dp[0][1] = max(v[0].fs,v[0].sc);
	dp[0][0] = v[0].fs;
	for(int i = 1;i<v.size();i++){
		dp[i][0] = dp[i-1][1]+v[i].fs;
		dp[i][1] = max({dp[i-1][0]+v[i].fs+1,dp[i-1][1]+v[i].sc,dp[i][0]});
	}
	re = max(re,dp[v.size()-1][1]);
	ans -= re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i =0;i<n;i++){
		cin>>tmp[i].fs>>tmp[i].sc;
		all.push_back(tmp[i].fs);
	}
	if(n&1){
		cout<<-1;
		return 0;
	}
	sort(all.begin(),all.end());
	for(int i = 0;i<n;i++){
		auto a = lower_bound(all.begin(),all.end(),tmp[i].fs)-all.begin()+1;
		auto b = lower_bound(all.begin(),all.end(),tmp[i].sc)-all.begin()+1;
		arr[a] = b;
		deg[b]++;
		jelly[b].push_back(a);
	}
	psyco.set();
	for(int i = 1;i<=n;i++){
		if(!deg[i])q.push(i);
	}
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		psyco[now] = false;
		deg[arr[now]]--;
		if(!deg[arr[now]]){
			q.push(arr[now]);
		}
	}
	for(int i = 1;i<=n;i++){
		if(psyco[i])dfs(i);
	}
	vector<pii> v;
	ans = n;
	for(int i = 1;i<=n;i++){
		if(vis[i]||!psyco[i])continue;
		v.clear();
		int now = i;
		do{
			v.push_back({dp[now][0],dp[now][1]});
			vis[now] = true;
			now = arr[now];
		}while(now != i);
		calc(v);
	}
	cout<<ans;
}

Compilation message (stderr)

polygon.cpp: In function 'void calc(std::vector<std::pair<int, int> >&)':
polygon.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 1;i<v.size();i++){
      |                ~^~~~~~~~~
polygon.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 1;i<v.size();i++){
      |                ~^~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25