Submission #880837

#	Time	Username	Problem	Language	Result	Execution time	Memory
880837		vjudge1	Love Polygon (BOI18_polygon)	C++17	0 / 100	51 ms	13548 KiB

polygon

#pragma GCC optimize("fast-math")
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC target("avx2")

#include<bits/stdc++.h>
     
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
#define pb              push_back
#define F               first
#define S               second
//#define mp              make_pair
#define all(x)          x.begin(),x.end()
#define file            freopen("txt.in", "r", stdin);freopen("txt.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; return 0;}
#define int                ll

const int N =  1e5 + 5, LG = 18, MOD = 1e9+9;// 998244353
const ll inf = 1e12;

int n, num;
vector<int> out[N], vec;
unordered_map<string, int> m;
bitset<N> mark;

void dfs(int v) {
    ++num;
//  cerr << v << ' ' << num << '\n';
    mark[v] = 1;
    for(int i : out[v])
        if(!mark[i]) 
            dfs(i);
    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n;
    int cnt = 1;
    for(int i = 0 ; i < n; ++i) {
        string v, u;    
        cin >> v >> u;
        if(m[v] == 0) m[v] = cnt++;
        if(m[u] == 0) m[u] = cnt++;
//        cerr << v << ' ' << m[v] << '\n';
//        cerr << u << ' ' << m[u] << '\n';
        out[m[v]].pb(m[u]);
    }
    
    if(n%2) kill(-1);


    int ans = 0, odds = 0;
    for(int i = 1; i <= n; ++i) {
        if(!mark[i]) {
            num = 0;
            dfs(i);
//            vec.pb(num);
            if(num == 2) continue;
            if(num % 2 == 0) ans += num/2;
            else {
                ans += num/2;
                ++odds;
            }
        }
    }
    
    cout << ans + odds/2 ;
    
    return 0;
}  

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