oj.uz

Submission #377003

# Submission time Handle Problem Language Result Execution time Memory
377003 2021-03-12T16:59:57 Z lertwqen243 Love Polygon (BOI18_polygon) C++14
0 / 100
 208 ms 34832 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    const int N = 1e5 + 5;
     
    int n,love[N];
    int ind;
    unordered_map<string,int>id;
    vector <int> g[N],adj[N];
    bool mrk[N];
    vector<int>ord,roots;
    void dfs(int v){
        mrk[v]=1;
        for (int i=0;i<(int)g[v].size();i++){
            int u=g[v][i];
            if (!mrk[u]){
                adj[v].push_back(u); 
                dfs(u);
            }
        }
        ord.push_back(v);
        return;
    }
    int used[N];
    int max_maching;
    bool mark[N];
    void maching_dfs(int v, int par){
        for (int i=0;i<(int)adj[v].size();i++){
            int u=adj[v][i];
            maching_dfs(u,v);
        }
        if (!used[v] && !used[par] && par!=0){
            max_maching++;
            used[v]=used[par]=1;
        }
    }
    inline int solve1(int root){
        max_maching = 0;
        for (int i=0;i<(int)ord.size();i++){
            int v=ord[i];
            used[v]=0;
        }
        maching_dfs(root,0);
        return max_maching;
    }
    inline int solve2(int root){
        if (love[root]==root) return 0;
        for (int i=0;i<(int)ord.size();i++){
            int v=ord[i];
            used[v]=0;
        }
        used[root]=used[love[root]]=1;
        max_maching=0;
        maching_dfs(root,0);
        return max_maching+1+(int)(love[love[root]]==root);
    }
    int main() {
        ios_base::sync_with_stdio(0),cin.tie(0);cout.tie(0);
        cin>>n;
        if (n%2){
            cout<<"-1\n";
            return 0;
        }
        for (int i=1;i<=n;i++){
            string a,b;
            cin>>a>>b;
            if (id.count(a)==0){
                id[a]=++ind;
            }
            if (id.count(b)==0){
                id[b]=++ind;
            }
            int u=id[a];
            int v=id[b];
            love[u]=v;
            g[v].push_back(u);
        }
        for (int i=1;i<=n;i++){
            mrk[i]=0;
            if(love[i]==i) roots.push_back(i);
        }
        int ans=n;
        for (int j=0;j<(int)roots.size();j++){
            int i=roots[j];
            int root=i;  
            ord.clear();dfs(root);
            ans-=solve1(root);
        }
        for(int i=1;i<=n;i++){adj[i] = {}; mrk[i]=0;}
        int ans2 = n;
        for(int i=1;i<=n;i++){
            if (mrk[i]) continue;
            int root=i;
            mark[i]=1;
            if (!mark[love[root]]){
                root=love[root];
                mark[root]=1;
            }   
            ord.clear();dfs(root);
            ans2-=max(solve2(root),solve1(root));
        }
        assert(ans2<ans);
        cout<<ans<<'\n';
        return 0;
    }

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 17936 KB Output is correct
2 Correct 208 ms 20752 KB Output is correct
3 Runtime error 107 ms 34832 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -