Submission #951576

#	Time	Username	Problem	Language	Result	Execution time	Memory
951576		huangallen	Love Polygon (BOI18_polygon)	C++17	100 / 100	92 ms	26092 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int,int>
#define pipii pair<int,pii>
#define Graph vector<vector<int>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld long double
#define pdd pair<ld,ld>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) cout<<(#x)<<":";REP(allen,(x).size()) cout<<x[allen]<<" ";cout<<" size="<<(x).size()<<endl;
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
const int mod=1e9+7;
const int maxn=255;
const int maxv=1e5+5;
const int inf=(1ll<<62);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {
    return uniform_int_distribution<int>(l,r)(rng);
}
//shuffle(a,a+n,rng)
//
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
//template<typename T> using pb_ds_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//
//using Tree = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
struct chash {
    int operator()(string s)const {
        int r=0;
        for(char c:s) r=(r<<4)+(r<<3)+(r<<1)+r+c-'a'+1;
        return r;
    }
};
unordered_map<string,int,chash> ump;
int n;
vector<int> to,ind;
vector<bool> inc,vis;
Graph gb;
int an=0;
pii dfs(int u) {//no,yes
    vis[u]=1;
    pii an={0,0};
    int mxs=0;
    for(int v:gb[u]) {
        if(vis[v]) continue;
        pii ret=dfs(v);
        an.f+=ret.s;
        mxs=max(mxs,ret.f-ret.s+1);
    }
    an.s=an.f+mxs;
    return an;
}
void vis_to_0(int u) {
    vis[u]=0;
    for(int v:gb[u]) {
        if(vis[v]) vis_to_0(v);
    }
}
void cal_j(int u) {
    int t=to[u],cnt=1,ret=0;
    while(t!=u) {
        cnt++;
        t=to[t];
    }
    if(cnt==1) ret+=dfs(u).s;
    else if(cnt==2) {
        ret=dfs(u).s;
        vis_to_0(u);
        vis[u]=1,vis[to[u]]=1;
        ret=max(ret,dfs(u).f+dfs(to[u]).f+2);
    }
    else {
        ret=dfs(u).s;
        vis_to_0(u);
        vis[u]=1;
        ret=max(ret,1+dfs(to[u]).f+dfs(u).f);
    }
    an+=ret;
}
signed main() {
    IOS();
    cin>>n;
    if(n&1) {
        cout<<"-1\n";
        return 0;
    }
    gb=Graph(n);
    to=vector<int>(n);
    ind=vector<int>(n);
    vector<string> in_s(n);
    inc=vector<bool>(n,1);
    vis=vector<bool>(n,0);
    REP(i,n) {
        string u;
        cin>>u>>in_s[i];
        ump[u]=i;
    }
    REP(i,n) {
        to[i]=ump[in_s[i]];
        ind[to[i]]++;
        gb[to[i]].pb(i);
    }
    queue<int> q;
    REP(i,n) if(ind[i]==0) q.push(i);
    while(q.size()) {
        int u=q.front();
        q.pop();
        inc[u]=0;
        ind[to[u]]--;
        if(ind[to[u]]==0) q.push(to[u]);
    }
//    oparr(inc)oparr(ind)
    REP(i,n) {
        if(inc[i]&&!vis[i]) cal_j(i);
    }
    an=n-an;
    cout<<an<<'\n';
    return 0;
}

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