Submission #675953

#	Time	Username	Problem	Language	Result	Execution time	Memory
675953		browntoad	Love Polygon (BOI18_polygon)	C++14	100 / 100	146 ms	27740 KiB

polygon

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define f first
#define s second
#define pb push_back
#define endl '\n'

const ll maxn = 1e5+5;
const ll inf = (1ll<<60);
vector<int> graph(maxn);
vector<int> rgraph[maxn];
vector<bool> occ(maxn);
int dpt[maxn][2];
int dpc[maxn][3];
vector<bool> incyc(maxn);
vector<int> siz(maxn);
vector<int> cycs;
void dfs(int x){
    if (incyc[graph[x]]) {
        incyc[x]=1;
        return;
    }
    if (occ[graph[x]]==0) {
        occ[graph[x]]=1;
        dfs(graph[x]);
        incyc[x]=1;
    }
    else {
        cycs.pb(x);
        incyc[x]=1;
    }
}
void dfs2(int x){
    int mn=0;
    REP(i, SZ(rgraph[x])){
        if (incyc[rgraph[x][i]]) continue;
        dfs2(rgraph[x][i]);
        dpt[x][0]+=dpt[rgraph[x][i]][1];
        dpt[x][1]+=dpt[rgraph[x][i]][1];
        mn=min(mn, dpt[rgraph[x][i]][0]-dpt[rgraph[x][i]][1]);
    }
    dpt[x][1]+=mn+1;
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin>>n;
    vector<string> pos(n);
    vector<pair<string, string> > Graph(n);
    REP(i, n){
        cin>>Graph[i].f>>Graph[i].s;
        pos[i]=Graph[i].f;
    }
    sort(ALL(pos));
    REP(i, n){
        int a=upper_bound(ALL(pos), Graph[i].f)-pos.begin();
        int b=upper_bound(ALL(pos), Graph[i].s)-pos.begin();
        graph[a]=b;
        rgraph[b].pb(a);
    }
    REP1(i, n){
        if (!occ[i]){
            occ[i]=1;
            dfs(i);
        }
    }

    int ans=0;
    fill(ALL(incyc), false);
    REP(i, SZ(cycs)){
        int cur = cycs[i];
        //cout<<cur<<endl;
        vector<pii> tmp;

        incyc[cur]=1;
        cur=graph[cur];
        while(cur!=cycs[i]){
            incyc[cur]=1;
            cur=graph[cur];
        }

        dfs2(cur);
        tmp.pb({dpt[cur][0], dpt[cur][1]});
        cur=graph[cur];
        while(cur!=cycs[i]){
            dfs2(cur);
            tmp.pb({dpt[cur][0], dpt[cur][1]});
            cur=graph[cur];
        }
        if (SZ(tmp)==1){
            ans+=tmp[0].s;
        }
        else if (SZ(tmp)==2){
            ans+=min(tmp[0].f+tmp[1].f, tmp[0].s+tmp[1].s);
        }
        else {
            int cans = inf;
            // first is 0
            dpc[0][0]=tmp[0].f;
            dpc[0][1]=dpc[0][2]=inf;
            REP1(j, SZ(tmp)-1){
                dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
                dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
                dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
            }
            cans=min({cans, dpc[SZ(tmp)-1][1], dpc[SZ(tmp)-1][2]});
            // second is 1
            dpc[0][1]=tmp[0].s;
            dpc[0][0]=dpc[0][2]=inf;
            REP1(j, SZ(tmp)-1){
                dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
                dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
                dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
            }
            cans=min({cans, dpc[SZ(tmp)-1][1], dpc[SZ(tmp)-1][2]});
            // third is 2
            dpc[0][2]=tmp[0].f+1;
            dpc[0][0]=dpc[0][1]=inf;
            REP1(j, SZ(tmp)-1){
                dpc[j][0]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].f);
                dpc[j][1]=min(inf, min(dpc[j-1][1], dpc[j-1][2])+tmp[j].s);
                dpc[j][2]=min(inf, dpc[j-1][0]+tmp[j].f+1);
            }
            cans=min(cans, dpc[SZ(tmp)-1][0]);

            ans+=cans;
        }
    }

    if (n%2==1) ans=-1;
    cout<<ans<<endl;
}

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