oj.uz

답안 #951575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951575 2024-03-22T06:54:59 Z huangallen Love Polygon (BOI18_polygon) C++17
29 / 100
 79 ms 25484 KB 
#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]).s+dfs(u).s);
    }
    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
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 79 ms 25032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 17604 KB Output is correct
2 Correct 64 ms 19652 KB Output is correct
3 Correct 53 ms 18120 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 70 ms 25484 KB Output is correct
6 Correct 59 ms 17380 KB Output is correct
7 Correct 71 ms 17420 KB Output is correct
8 Correct 57 ms 17348 KB Output is correct
9 Correct 54 ms 17092 KB Output is correct
10 Correct 40 ms 16836 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -