Submission #1031340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031340		codexistent	Love Polygon (BOI18_polygon)	C++14	0 / 100	243 ms	25164 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define f first
#define s second

int n, d[MAXN], pn[MAXN], vd[MAXN], gn = 0, gi = 0, r = 0;
string s[MAXN];
pair<string, string> e[MAXN];
map<string, int> pos;
vector<int> ie[MAXN];

stack<int> sk;
set<int> st;

void dfs(int i){
    if(d[i] >= 0 && vd[i] != gn) return;
    d[i] = 0, vd[i] = gn;

    if(st.find(i) != st.end()){
        //cout << "NEVAH!" << endl;
        int prv = i;
        while(sk.top() != i){
            d[sk.top()] = gn;
            pn[prv] = sk.top();
            sk.pop();
        }
        d[sk.top()] = gn;
        sk.pop();
        return;
    }
    st.insert(i);
    sk.push(i);

    /*cout << "at " << e[i].f << "/" << i << " we have the set: " << endl;
    for(int i : st){
        cout << " => " << i << endl;
    } */
    
    dfs(pos[e[i].s]);
}

int main(){
    cin >> n;
    FOR(i, 1, n) {
        cin >> e[i].f >> e[i].s;
        s[i] = e[i].f;
        pos.insert({s[i], i});
        d[i] = -1;
    }

    if(n % 2 == 1) {
        cout << -1 << endl;
        return 0;
    }

    FOR(i, 1, n){
        ie[pos[e[i].s]].push_back(i); 
        if(pos[e[pos[e[i].s]].s] == i){
            d[i] = -2;
        }
    }

    FOR(i, 1, n){  
        if(d[i] == -1){
            gn++, dfs(i);
            stack<int>().swap(sk), st.clear();
        }
    }

    int l = 0;
    FOR(i, 1, n){
        if(ie[i].size() == 0 && d[i] >= 0){
            int prv = i;
            bool cnx = true;
            while(d[pos[e[i].s]] == 0){
                if(cnx){
                    d[prv] = d[pos[e[i].s]] = -1;
                    r++;
                    cnx = false;
                }else{
                    prv = pos[e[i].s];
                    cnx = true;
                }
            }

            if(cnx){
                if(d[pos[e[i].s]] >= 1){
                    d[pos[e[i].s]] = d[i] = -1;
                    r++;
                }else{
                    l++;
                }
            }
        }
    }

    FOR(i, 1, n){
        if(d[i] >= 1){
            d[i] = -1;
            int sc = 1, a = i, b = i;
            while(d[pn[a]] >= 1 && pn[a] != b) {
                a = pn[a];
                d[a] = -1;
                sc++;
            }
            while(d[pos[e[b].s]] >= 1 && pos[e[b].s] != a) {
                b = pos[e[b].s];
                d[b] = -1;
                sc++;
            }

            r += sc / 2;
            if(sc % 2){
                l++;
            }
        }
    }

    cout << (r + l) << endl;
}

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