Submission #1280983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280983		HoriaHaivas	Love Polygon (BOI18_polygon)	C++20	54 / 100	297 ms	27904 KiB

polygon

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

map<string,int> mp;
map<int,bool> in_cycle;
int nxt[100005];
bool visited[100005];
vector<int> curr_cycle;
vector<int> in_edge[100005];
int dp[100005][2];
int dp2[100005][2];
int cnt;
int ans;
bool ret;
int gettem;
int actual_sz;
int remain;

void dfs(int node)
{
    if (visited[node])
    {
        ret=true;
        gettem=node;
        return;
    }
    visited[node]=1;
    dfs(nxt[node]);
    if (ret==true)
    {
        curr_cycle.push_back(node);
        in_cycle[node]=1;
        if (gettem==node)
            ret=false;
    }
}

void dfs2(int node)
{
    visited[node]=1;
    actual_sz++;
    int s,mx;
    s=0;
    for (auto x : in_edge[node])
    {
        dfs2(x);
        s+=max(dp[x][1],dp[x][0]);
    }
    dp[node][0]=s;
    mx=0;
    for (auto x : in_edge[node])
        mx=max(mx,s-max(dp[x][1],dp[x][0])+dp[x][0]+1);
    dp[node][1]=mx;
}

void compute_dp(int root)
{
    int s,mx;
    s=0;
    for (auto x : in_edge[root])
    {
        if (in_cycle.find(x)==in_cycle.end())
        {
            dfs2(x);
            s+=max(dp[x][1],dp[x][0]);
        }
    }
    dp[root][0]=s;
    mx=0;
    for (auto x : in_edge[root])
    {
        if (in_cycle.find(x)==in_cycle.end())
            mx=max(mx,s-max(dp[x][1],dp[x][0])+dp[x][0]+1);
    }
    dp[root][1]=mx;
}

void solve()
{
    actual_sz=curr_cycle.size();
    for (auto x : curr_cycle)
    {
        compute_dp(x);
    }
    if (curr_cycle.size()==2)
    {
        remain-=2;
        return;
    }
    if (curr_cycle.size()==1)
    {
        ans+=max(dp[curr_cycle[0]][0],dp[curr_cycle[0]][1]);
        return;
    }
    int mx,i;
    mx=0;
    dp2[0][1]=max(dp[curr_cycle[0]][1],dp[curr_cycle[0]][0]);
    dp2[0][0]=dp[curr_cycle[0]][0];
    for (i=1; i<curr_cycle.size(); i++)
    {
        dp2[i][1]=max(dp2[i-1][0]+dp[curr_cycle[i]][0]+1,max(dp2[i-1][0],dp2[i-1][1])+max(dp[curr_cycle[i]][1],dp[curr_cycle[i]][0]));
        dp2[i][0]=max(dp2[i-1][1],dp2[i-1][0])+dp[curr_cycle[i]][0];
    }
    mx=max(mx,max(dp2[curr_cycle.size()-1][1],dp2[curr_cycle.size()-1][0]));
    ///avem un caz dubios : cuplam 1 cu n => hai sa il tratam separat
    dp2[0][1]=dp[curr_cycle[0]][0]+dp[curr_cycle.size()-1][0]+1;
    dp2[0][0]=-1e9;
    for (i=1; i<curr_cycle.size()-1; i++)
    {
        dp2[i][1]=max(dp2[i-1][0]+dp[curr_cycle[i]][0]+1,max(dp2[i-1][0],dp2[i-1][1])+max(dp[curr_cycle[i]][1],dp[curr_cycle[i]][0]));
        dp2[i][0]=max(dp2[i-1][1],dp2[i-1][0])+dp[curr_cycle[i]][0];
    }
    mx=max(mx,max(dp2[curr_cycle.size()-2][1],dp2[curr_cycle.size()-2][0]));
    ans+=mx;
}

signed main()
{
    /*
    ifstream fin("memes.in");
    ofstream fout("memes.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,casafiefrumos;
    string s1,s2;
    cin >> n;
    cnt=0;
    for (i=1; i<=n; i++)
    {
        cin >> s1 >> s2;
        if (mp[s1]==0)
            mp[s1]=++cnt;
        if (mp[s2]==0)
            mp[s2]=++cnt;
        nxt[mp[s1]]=mp[s2];
        in_edge[mp[s2]].push_back(mp[s1]);
    }
    if (n%2==1)
    {
        cout << "-1\n";
        return 0;
    }
    cnt=0;
    ans=0;
    remain=n;
    for (i=1; i<=n; i++)
    {
        if (!visited[i])
        {
            cnt++;
            curr_cycle.clear();
            in_cycle.clear();
            ret=false;
            dfs(i);
            solve();
        }
    }
    remain-=ans*2;
    casafiefrumos=ans+remain;
    cout << casafiefrumos;
    return 0;
}

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