oj.uz

답안 #880825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880825 2023-11-30T06:20:11 Z vjudge1 Love Polygon (BOI18_polygon) C++17
46 / 100
 716 ms 28672 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> adj[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 : adj[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]);
  }
  if (s.size() == pt){
    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 {
    FOR (i, 1, pt + 1){
      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:125: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]
  125 |   if (s.size() == pt){
      |       ~~~~~~~~~^~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 693 ms 21560 KB Output is correct
2 Correct 687 ms 21340 KB Output is correct
3 Correct 684 ms 21336 KB Output is correct
4 Correct 4 ms 21340 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 716 ms 21556 KB Output is correct
8 Correct 691 ms 21556 KB Output is correct
9 Correct 690 ms 21560 KB Output is correct
10 Correct 713 ms 21560 KB Output is correct
11 Correct 687 ms 21492 KB Output is correct
12 Correct 5 ms 21340 KB Output is correct
13 Correct 4 ms 21412 KB Output is correct
14 Correct 4 ms 21340 KB Output is correct
15 Correct 4 ms 21340 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 4 ms 21340 KB Output is correct
4 Correct 235 ms 28240 KB Output is correct
5 Correct 227 ms 25616 KB Output is correct
6 Correct 231 ms 28672 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 236 ms 23908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 693 ms 21560 KB Output is correct
2 Correct 687 ms 21340 KB Output is correct
3 Correct 684 ms 21336 KB Output is correct
4 Correct 4 ms 21340 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 716 ms 21556 KB Output is correct
8 Correct 691 ms 21556 KB Output is correct
9 Correct 690 ms 21560 KB Output is correct
10 Correct 713 ms 21560 KB Output is correct
11 Correct 687 ms 21492 KB Output is correct
12 Correct 5 ms 21340 KB Output is correct
13 Correct 4 ms 21412 KB Output is correct
14 Correct 4 ms 21340 KB Output is correct
15 Correct 4 ms 21340 KB Output is correct
16 Correct 4 ms 21336 KB Output is correct
17 Correct 4 ms 21340 KB Output is correct
18 Correct 4 ms 21340 KB Output is correct
19 Correct 235 ms 28240 KB Output is correct
20 Correct 227 ms 25616 KB Output is correct
21 Correct 231 ms 28672 KB Output is correct
22 Correct 1 ms 6748 KB Output is correct
23 Incorrect 236 ms 23908 KB Output isn't correct
24 Halted 0 ms 0 KB -