Submission #1259909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259909		niepamietamhasla	Love Polygon (BOI18_polygon)	C++20	100 / 100	133 ms	22760 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;

int DPd[MAXN][2];
int dokad[MAXN];
vector<int> graf[MAXN];

map<string, int> scal;
int T = 1;

int ans = 0;
int DP[MAXN];
int odw[MAXN];


vector<int> curr;
vector<int> cykl;

void znajdz(int a, int b){
    bool c = false;
    for(auto u : curr){
        //cout << u << " curr\n";
        if(u == a) c = true;
        if(c) cykl.push_back(u);
        if(u == b) c = false;
    }
    //cout << "end\n";
    return;
}

void dfsrev(int v, int p){
    if(odw[v] == 3) return;
    //cout << v << " " << p << " rev\n";
    odw[v] = 2;
    for(auto u : graf[v]){
        if(u == p) continue;
        dfsrev(u, v);
    }
    return;
}

void dfscykl(int v, int p){
    curr.push_back(v);
    odw[v] = 1;
    if(dokad[v] == v){
        cykl = {v};
        return;
    }
    if(odw[dokad[v]] == 1){
        znajdz(dokad[v], v);
        return;
    }
    else if(odw[dokad[v]] == 0){
        dfscykl(dokad[v], v);
    }
    curr.pop_back();
    odw[v] = 2;
    return;
}

void dfsdp(int v, int p){
    if(graf[v].size() == 1 and graf[v][0] == p){
        DPd[v][0] = 0;
        DPd[v][1] = 1;
        return;
    }
    else if(graf[v].size() == 1 and p == -1){
        DPd[v][0] = 0;
        DPd[v][1] = 1;
        return;
    }
    int S = 0;
    int mi = 1e9;
    for(auto u : graf[v]){
        if(u == p or odw[u] == 3) continue;
        dfsdp(u, v);
        S += DPd[u][1];
        mi = min(mi, DPd[u][0] - DPd[u][1]);
    }
    DPd[v][0] = S;
    DPd[v][1] = min(S + 1, S + mi + 1);
    return;
}
int obliczdp(){
    DP[0] = 0;
    DP[1] = DPd[cykl[0]][1];
    for(int i = 2; i <= cykl.size(); ++i){
        int x = cykl[i-1];
        DP[i] = min(DPd[x][1] + DP[i-1], DPd[x][0] + (dokad[x] == cykl[i-2] ? 0 : 1) + DPd[cykl[i-2]][0] + DP[i-2]);
    }
    return DP[cykl.size()];
}

void solve(int start){
    //cout << start << " st\n";
    dfscykl(start, -1);
    if(cykl.size() == 1){
        for(auto g : graf[cykl[0]]){
            dfsrev(g, cykl[0]);
        }
        dfsdp(cykl[0], cykl[0]);
        ans += DPd[cykl[0]][1];
        return;
    }
    if(dokad[cykl[0]] != cykl[1]){
        reverse(cykl.begin(), cykl.end());
    }
    for(auto u : cykl){
        odw[u] = 3;
    }
    for(auto u : cykl){
        for(auto g : graf[u]){
            dfsrev(g, u);
        }
        dfsdp(u, -1);
    }
    int tmp = obliczdp();
    int st = cykl[0];
    cykl.erase(cykl.begin());
    cykl.push_back(st);
    ans += min(tmp, obliczdp());
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s1, s2;
    for(int i = 0; i < n; ++i){
        cin >> s1 >> s2;
        int i1, i2;
        if(scal[s1] != 0)  i1 = scal[s1];
        else{
            scal[s1] = T;
            T++;
            i1 = T-1;
        }
        if(scal[s2] != 0) i2 = scal[s2];
        else{
            scal[s2] = T;
            i2 = T;
            T++;
        }
        if(i1 != i2) graf[i2].push_back(i1);
        dokad[i1] = i2;
    }
    if(n % 2 == 1){
        cout << -1 << "\n";
        return 0;
    }
    // for(auto u : scal){
    //     cout << u.first << " " << u.second << " scal\n";
    // }
    for(int i = 1; i <= n; ++i){
        if(odw[i] != 0) continue;
        cykl.clear();
        curr.clear();
        solve(i);
    }   
    cout << ans << "\n";
    return 0;
}

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