oj.uz

Submission #645232

# Submission time Handle Problem Language Result Execution time Memory
645232 2022-09-26T13:22:24 Z mychecksedad Love Polygon (BOI18_polygon) C++17
21 / 100
 301 ms 79316 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

int n, to[N], res = 0;
string x, y;
vector<int> in(N);
map<string, int> s;
vector<int> g[N];
vector<bool> vis(N);

void dfs(int v, int d){
    vis[v] = 1;
    assert(g[v].size()>1);
    for(int u: g[v]){
        if(vis[u]){
            if(d > 2) res += (d+1)/2;
            else if(d == 1) res++;
        }else dfs(u, d + 1);
    }
}


void solve(){
    cin >> n;
    int c = 1;
    for(int i = 0; i < n; ++i){
        cin >> x >> y;
        if(s[x] == 0) s[x] = c++;
        if(s[y] == 0) s[y] = c++;
        to[s[x] - 1] = s[y] - 1;
        g[s[x]-1].pb(s[y]-1);
    }
    if(n&1){
        cout << -1;
        return;
    }
    if(n <= 20){
        int ans = n;
        for(int mask = 0; mask < (1<<n); ++mask){

            bool ok = 1;
            vector<int> v;

            for(int j = 0; j < n; ++j){
                if(!((1<<j)&mask)){
                    v.pb(to[j]);
                    if(to[j] == j) ok = 0;
                    else if(!(to[to[j]] == j || ((1<<to[j])&mask))) ok = 0;
                }
            }
            sort(all(v));
            
            for(int j = 0; j < int(v.size()) - 1; ++j) if(v[j] == v[j + 1]) ok = 0;
            

            if(ok){
                if(ans > __builtin_popcount(mask)){
                    ans = __builtin_popcount(mask);
                }
            }
        }
        cout << ans;
        return;
    }

    for(int i = 0; i < n; ++i) if(!vis[i]) dfs(i, 1);
    cout << res;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

polygon.cpp: In function 'int main()':
polygon.cpp:87:16: warning: unused variable 'aa' [-Wunused-variable]
   87 |     int T = 1, aa;
      |                ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 27860 KB Output is correct
2 Correct 228 ms 27824 KB Output is correct
3 Correct 275 ms 27860 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 13 ms 27860 KB Output is correct
6 Correct 14 ms 27816 KB Output is correct
7 Correct 268 ms 27860 KB Output is correct
8 Correct 285 ms 27732 KB Output is correct
9 Correct 279 ms 27860 KB Output is correct
10 Correct 277 ms 27732 KB Output is correct
11 Correct 275 ms 27800 KB Output is correct
12 Correct 14 ms 27848 KB Output is correct
13 Correct 14 ms 27788 KB Output is correct
14 Correct 13 ms 27780 KB Output is correct
15 Correct 16 ms 27732 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 13 ms 27804 KB Output is correct
3 Correct 13 ms 27756 KB Output is correct
4 Runtime error 259 ms 79292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 79316 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 27860 KB Output is correct
2 Correct 228 ms 27824 KB Output is correct
3 Correct 275 ms 27860 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 13 ms 27860 KB Output is correct
6 Correct 14 ms 27816 KB Output is correct
7 Correct 268 ms 27860 KB Output is correct
8 Correct 285 ms 27732 KB Output is correct
9 Correct 279 ms 27860 KB Output is correct
10 Correct 277 ms 27732 KB Output is correct
11 Correct 275 ms 27800 KB Output is correct
12 Correct 14 ms 27848 KB Output is correct
13 Correct 14 ms 27788 KB Output is correct
14 Correct 13 ms 27780 KB Output is correct
15 Correct 16 ms 27732 KB Output is correct
16 Correct 13 ms 27732 KB Output is correct
17 Correct 13 ms 27804 KB Output is correct
18 Correct 13 ms 27756 KB Output is correct
19 Runtime error 259 ms 79292 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -