Submission #1032895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032895		anango	Love Polygon (BOI18_polygon)	C++17	100 / 100	587 ms	39984 KiB

polygon

#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF = 1LL<<30;

vector<vector<int>> adjlist,revadjlist;
//revadjlist = original adjlist, adjlist is the reversed version

vector<int> dp0;
vector<int> dp1;

//dp0 = maximum set of unmoved vertices choosable if this vertex is taken, dp1 if it's not taken


signed main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
    /*#ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif*/ //fast IO
    int n; cin >> n;
    adjlist=vector<vector<int>>(n);
    revadjlist=vector<vector<int>>(n);
    dp0=vector<int>(n,0);
    dp1=vector<int>(n,0);
    map<string,int> names;
    int ct=0;
    vector<int> sources;
    vector<int> child(n);
    vector<set<int>> parents(n);
    for (int i=0; i<n; i++) {
        string s,t; cin >> s >> t;
        if (!names.count(s)) {
            names[s] = ct;
            ct++;
        }
        if (!names.count(t)) {
            names[t] = ct;
            ct++;
        }
        revadjlist[names[s]].push_back(names[t]);
        child[names[s]]=names[t];
        parents[names[t]].insert(names[s]);
        if (s==t) {
            sources.push_back(names[s]);
            continue;
        }
        adjlist[names[s]].push_back(names[t]);
        adjlist[names[t]].push_back(names[s]);
    }
    if (n%2==1) {
        cout << -1 << endl; return 0;
    }
    int ops=0;
    set<int> active;
    for (int i=0; i<n; i++) active.insert(i);
    for (int i=0; i<n; i++) {
        if (active.count(i) && active.count(child[i]) && i!=child[i] && i==child[child[i]]) {
            //cout << "easy remove" << " " << i <<" " << child[i] << endl;
            active.erase(i); active.erase(child[i]);
        }
    }
    vector<int> vals;
    for (int i=0; i<n; i++) {
        if (parents[i].size()==0) {
            vals.push_back(i);
        }
    }

    while (active.size()) {
        if (!vals.size()) vals.push_back(*active.begin());
        //do a BFS, if it's the last parent of a child, add the child
        int rem = vals.back(); vals.pop_back();
        ops++;
        active.erase(rem);
        parents[child[rem]].erase(rem);
        //cout << "removing " << rem <<" " << child[rem] << endl;
        if (active.count(child[rem])) {
            active.erase(child[rem]);
            parents[child[child[rem]]].erase(child[rem]);
            if (active.count(child[child[rem]]) && parents[child[child[rem]]].size()==0) {
                vals.push_back(child[child[rem]]);
            }
        }
    }
    cout << ops << endl;

    
    
}

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