Submission #680555

#	Time	Username	Problem	Language	Result	Execution time	Memory
680555		Cross_Ratio	Love Polygon (BOI18_polygon)	C++14	100 / 100	282 ms	30148 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
map<string, int> M;
vector<vector<int>> adj;
int type[100005];
bool vis[100005];
vector<int> V;
int no1 = -1, no2 = -1;
array<int, 2> dfs(int c, int p) {
    int d0 = 0, d1 = -1e9;
    int sum = 0;
    vis[c] = true;
    V.push_back(c);
    int cnt = 0;
    for(int n : adj[c]) {
        if(n==p || vis[n]) continue;
        if(c==no1&&n==no2) continue;
        if(c==no2&&n==no1) continue;
        array<int, 2> k = dfs(n, c);
        d0 += max(k[0], k[1]);
        sum += k[1];
        d1 = max(d1, k[0] - k[1]);
        cnt++;
    }
    d1 = sum + d1;
    if(cnt==0) return {0, 0};
    return {d0, 1 + d1};
}
bool vis2[100005];
array<int, 2> dfs2(int c, int p) {
    vis2[c] = true;
    for(int n :adj[c]) {
        if(n==p) continue;
        if(n==c) return {-2, c};
        if(vis2[n]) return {c, n};
        array<int, 2> k = dfs2(n, c);
        if(k[0]==-2) return k;
        if(k[0]>=0) return k;
    }
    return {-1, -1};
}
set<array<int, 2>> Ed;
array<int, 2> Edge[100005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int cnt = 0;
    int i, j;
    adj.resize(N);
    for(i=0;i<N;i++) {
        string s1, s2;
        cin >> s1 >> s2;
        int v1 = -1, v2 = -1;
        if(M.count(s1)) v1 = M[s1];
        else {
            M[s1] = v1 = cnt;
            cnt++;
        }
        if(M.count(s2)) v2 = M[s2];
        else {
            M[s2] = v2 = cnt;
            cnt++;
        }
        //adj[v1].push_back(v2);
        //adj[v2].push_back(v1);
        Edge[i] = {v1, v2};
        Ed.insert(Edge[i]);
    }
    if(N%2==1) {
        cout << "-1";
        return 0;
    }
    for(i=0;i<N;i++) type[i] = -1;
    int ans = 0;
    for(i=0;i<N;i++) {
        array<int, 2> re = {Edge[i][1], Edge[i][0]};
        if(Edge[i][0]==Edge[i][1]) continue;
        if(vis[Edge[i][0]] || vis[Edge[i][1]]) continue;
        if(Ed.find(re)!=Ed.end()) {
            vis[Edge[i][0]] = vis[Edge[i][1]] = true;
            vis2[Edge[i][0]] = vis2[Edge[i][1]] = true;
            ans += 2;
        }
    }
    for(i=0;i<N;i++) {
        if(!vis[Edge[i][0]] && !vis[Edge[i][1]] && Edge[i][0]!=Edge[i][1]) {
            adj[Edge[i][0]].push_back(Edge[i][1]);
            adj[Edge[i][1]].push_back(Edge[i][0]);
        }
    }
    for(i=0;i<N;i++) {
        if(!vis2[i]) {
            array<int, 2> backedge = dfs2(i, -1);
            int x = backedge[0], y = backedge[1];
            //cout << "BackEdge is " << x << ' ' << y  << '\n';
            if(x<0) {
                if(x==-1) y = i;
                V.clear();
                array<int, 2> k = dfs(y, -1);
                for(int n : V) vis2[n] = true;
                ans += max(k[0], k[1]);
                //cout << k[0] << ' ' << k[1] << '\n';
                continue;
            }
            V.clear();
            vis[x] = vis[y] = true;
            int ma = 0;
            int val = 0;
            no1 = no2 = -1;
            for(int n : adj[y]) {
                if(!vis[n]) {
                    array<int, 2> k = dfs(n, -1);
                    val += max(k[0], k[1]);
                }
            }
            for(int n : adj[x]) {
                if(!vis[n]) {
                    array<int, 2> k = dfs(n, -1);
                    val += max(k[0], k[1]);
                }
            }
            val++;
            ma = max(ma, val);
            no1 = y, no2 = x;
            vis[x] = vis[y] = false;
            for(int k : V) vis2[k] = true;
            for(int k : V) vis[k] = false;
            V.clear();
            val = 0;
            if(!vis[x]) {
                array<int, 2> k = dfs(x, -1);
                val += max(k[0], k[1]);
            }
            if(!vis[y]) {
                array<int, 2> k = dfs(y, -1);
                val += max(k[0], k[1]);
            }
            for(int n : V) vis2[n] = true;
            V.clear();
            ma = max(ma, val);
            ans += ma;
            //cout << i << " : " << ans << '\n';
        }
    }
    cout << N - ans;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:51:12: warning: unused variable 'j' [-Wunused-variable]
   51 |     int i, j;
      |            ^

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