oj.uz

Submission #880849

# Submission time Handle Problem Language Result Execution time Memory
880849 2023-11-30T07:09:01 Z vjudge1 Love Polygon (BOI18_polygon) C++17
25 / 100
 83 ms 16324 KB 
#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, indeg[N];
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]);
        ++indeg[m[u]];
    }
    
    if(n%2) kill(-1);

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

    cout << ans + odds ;
    return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 67 ms 15996 KB Output is correct
5 Correct 65 ms 14276 KB Output is correct
6 Correct 62 ms 16324 KB Output is correct
7 Correct 53 ms 14192 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 14788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -