oj.uz

Submission #880835

# Submission time Handle Problem Language Result Execution time Memory
880835 2023-11-30T06:42:22 Z vjudge1 Love Polygon (BOI18_polygon) C++17
75 / 100
 741 ms 39472 KB 
/// I'm only brave when I have to be
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;

template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;

constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 1e5, SQ = 300, INF = 2e18 + 8, LGN = 21, mod = 998244353, P = 131113;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool mark[N], used[N];
int n, pt, sz, ans, mat[25][25], dp[(1<<LGN)];
map <string, int> m;
vector <int> v;
vector <int> adj[N];
vector <int> adj2[N];

void dfs (int u){
  mark[u] = true;
  ++ sz;
  for (int i : adj[u]){
    if (!mark[i]){
      dfs (i);
    }
  }
  return;
}

void dfs2 (int u, int par = -1){
  mark[u] = true;
  for (int i : adj2[u]){
    if (!mark[i]){
      dfs2 (i, u);
    }
  }
  if (par != -1 && !used[u] && !used[par]){
    ++ ans;
    used[u] = true;
    used[par] = true;
  }
  return;
}

int32_t main(){
  fast_io;
  cin >> n;
  if (n & 1){
    cout << -1;
    return 0;
  }
  if (n <= 20){
    set <string> s;
    FOR (i, 0, n){
      string ss, tt;
      cin >> ss >> tt;
      if (s.find(ss) == s.end()){
        m[ss] = pt ++;
        s.insert(ss);
      }
      if (s.find(tt) == s.end()){
        m[tt] = pt ++;
        s.insert(tt);
      }
      mat[m[ss]][m[tt]] = 1;
      //cout << m[ss] << " " << m[tt] << '\n';
    }
    fill (dp, dp + (1 << LGN), INF);
    dp[0] = 0;
    for (int i = 1; i < (1 << n); ++ i){
      for (int j = 0; j < n; ++ j){
        if (i & (1 << j)){
          for (int k = 0; k < n; ++ k){
            if ((i & (1 << k)) && j != k){
              dp[i] = min (dp[i], dp[i^(1<<j)^(1<<k)] + 2 - mat[j][k] - mat[k][j]);
              //cout << i << " updated from " << (i^(1<<j)^(1<<k)) << " " << dp[i^(1<<j)^(1<<k)] << "  " << j << " " << k << " : " << mat[j][k] << " " << mat[k][j] << '\n';
            }
          }
        }
      }
      //cout << i << " " << dp[i] << '\n';
    }
    cout << dp[(1<<n)-1];
    return 0;
  }
  set <string> s;
  FOR (i, 0, n){
    string ss, tt;
    cin >> ss >> tt;
    s.insert(tt);
    if (m[ss] == 0){
      m[ss] = ++ pt;
    }
    if (m[tt] == 0){
      m[tt] = ++ pt;
    }
    adj[m[ss]].pb(m[tt]);
    adj2[m[tt]].pb(m[ss]);
    if (ss == tt){
      v.pb(m[ss]);
    }
  }
  if (s.size() == pt){
    if (pt & 1){
      cout << -1;
      return 0;
    }
    for (int i = 1; i <= n; ++ i){
      if (!mark[i]){
        dfs (i);
        if (sz == 2){
          sz = 0;
          continue;
        }
        ans += (sz + 1) / 2;
        sz = 0;
      }
    }
    cout << ans;
  }
  else {
    if (pt & 1){
      cout << -1;
    }
    for (int i : v){
      if (!mark[i]){
        dfs2 (i);
      }
    }
    cout << pt - ans << '\n';
  }
  return 0;
}

// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present

Compilation message

polygon.cpp: In function 'int32_t main()':
polygon.cpp:131:16: warning: comparison of integer expressions of different signedness: 'std::set<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  131 |   if (s.size() == pt){
      |       ~~~~~~~~~^~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 26252 KB Output is correct
2 Correct 716 ms 26204 KB Output is correct
3 Correct 719 ms 26260 KB Output is correct
4 Correct 6 ms 26200 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 714 ms 26260 KB Output is correct
8 Correct 723 ms 26256 KB Output is correct
9 Correct 725 ms 26256 KB Output is correct
10 Correct 733 ms 26456 KB Output is correct
11 Correct 725 ms 26252 KB Output is correct
12 Correct 5 ms 26200 KB Output is correct
13 Correct 5 ms 26520 KB Output is correct
14 Correct 5 ms 26460 KB Output is correct
15 Correct 5 ms 26204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26204 KB Output is correct
2 Correct 5 ms 26204 KB Output is correct
3 Correct 5 ms 26204 KB Output is correct
4 Correct 323 ms 35600 KB Output is correct
5 Correct 301 ms 32920 KB Output is correct
6 Correct 305 ms 35920 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 30280 KB Output is correct
2 Correct 297 ms 34352 KB Output is correct
3 Correct 241 ms 35780 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 307 ms 39472 KB Output is correct
6 Correct 255 ms 29868 KB Output is correct
7 Correct 308 ms 29876 KB Output is correct
8 Correct 274 ms 31592 KB Output is correct
9 Correct 216 ms 27732 KB Output is correct
10 Correct 136 ms 24772 KB Output is correct
11 Correct 38 ms 26204 KB Output is correct
12 Correct 6 ms 26204 KB Output is correct
13 Correct 5 ms 26204 KB Output is correct
14 Correct 37 ms 26276 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 26252 KB Output is correct
2 Correct 716 ms 26204 KB Output is correct
3 Correct 719 ms 26260 KB Output is correct
4 Correct 6 ms 26200 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 714 ms 26260 KB Output is correct
8 Correct 723 ms 26256 KB Output is correct
9 Correct 725 ms 26256 KB Output is correct
10 Correct 733 ms 26456 KB Output is correct
11 Correct 725 ms 26252 KB Output is correct
12 Correct 5 ms 26200 KB Output is correct
13 Correct 5 ms 26520 KB Output is correct
14 Correct 5 ms 26460 KB Output is correct
15 Correct 5 ms 26204 KB Output is correct
16 Correct 6 ms 26204 KB Output is correct
17 Correct 5 ms 26204 KB Output is correct
18 Correct 5 ms 26204 KB Output is correct
19 Correct 323 ms 35600 KB Output is correct
20 Correct 301 ms 32920 KB Output is correct
21 Correct 305 ms 35920 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 273 ms 30280 KB Output is correct
24 Correct 297 ms 34352 KB Output is correct
25 Correct 241 ms 35780 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 307 ms 39472 KB Output is correct
28 Correct 255 ms 29868 KB Output is correct
29 Correct 308 ms 29876 KB Output is correct
30 Correct 274 ms 31592 KB Output is correct
31 Correct 216 ms 27732 KB Output is correct
32 Correct 136 ms 24772 KB Output is correct
33 Correct 38 ms 26204 KB Output is correct
34 Correct 6 ms 26204 KB Output is correct
35 Correct 5 ms 26204 KB Output is correct
36 Correct 37 ms 26276 KB Output is correct
37 Incorrect 272 ms 33792 KB Output isn't correct
38 Halted 0 ms 0 KB -