Submission #521725

#	Time	Username	Problem	Language	Result	Execution time	Memory
521725		Yazan_Alattar	Love Polygon (BOI18_polygon)	C++14	100 / 100	200 ms	24876 KiB

polygon

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

set < pair <string,int> > s; int tot;
int compress(string x)
{
    auto it = s.lower_bound(make_pair(x, 0));
    if(it == s.end() || (*it).F != x){
        s.insert({x, ++tot});
        return tot;
    }
    return (*it).S;
}

bool vist[M], oncycle[M], done[M];

int get(vector <int> v)
{
    int n = v.size();
    int ret = 0;
    for(auto i : v) ret |= i;
    if(!ret) return n / 2;
    ret = 0;
    for(int i = 0; i < n; ++i){
        int j = (i + 1) % n;
        if(v[i] && !v[j]){
            int len = 0;
            while(!v[j]){
                ++len;
                j = (j + 1) % n;
            }
            ret += len / 2;
        }
    }
    return ret;
}

vector <int> adj[M];
int n, p[M], ans, mx[M];

void calc(int node)
{
    vist[node] = 1;
    for(auto i : adj[node]) if(!oncycle[i]){
        calc(i);
        mx[node] += mx[i];
        if(!done[i]) done[node] = 1;
    }
    if(done[node]) ++mx[node];
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    if(n % 2) return cout << -1 << endl, 0;
    for(int i = 1; i <= n; ++i){
        string x, y;
        cin >> x >> y;
        int a = compress(x);
        int b = compress(y);
        p[a] = b;
        adj[b].pb(a);
    }
    for(int i = 1; i <= n; ++i) if(!vist[i]){
        int cur = i;
        while(!vist[cur]){
            vist[cur] = 1;
            cur = p[cur];
        }
        vector <int> cycle;
        int st = cur;
        while(1){
            cycle.pb(cur);
            oncycle[cur] = 1;
            cur = p[cur];
            if(cur == st) break;
        }
        vector <int> v;
        int ret = 0;
        for(auto j : cycle){
            calc(j);
            ret += mx[j];
            v.pb(done[j]);
        }
        if(cycle.size() == 2) ret = ret - v[0] - v[1] + 2;
        else ret += get(v);
        ans += ret;
    }
    cout << n - ans << endl;
    return 0;
}

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