oj.uz

Submission #952428

# Submission time Handle Problem Language Result Execution time Memory
952428 2024-03-23T21:13:24 Z Yell0 Love Polygon (BOI18_polygon) C++17
29 / 100
 83 ms 27172 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int MN=1e5+2;
int N;
vector<int> fromgr[MN];
int togr[MN];
bool vis[MN];
int dpst[MN], dpew[MN];

void dfs(int u, int root) {
  vis[u] = 1;
  if(fromgr[u].empty()) {
    dpst[u] = 1;
    dpew[u] = 0;
    return;
  }
  dpst[u] = 1e9;
  dpew[u] = 0;
  for(int v : fromgr[u]) {
    if(v == root) continue;
    dfs(v, root);
    dpew[u] += dpst[v];
  }
  for(int v : fromgr[u]) {
    if(v == root) continue;
    dpst[u] = min(dpst[u], dpew[u] - dpst[v] + dpew[v] + 1);
  }
}

int solve(int u) {
  vector<bool> seen(N, 0);
  // find root
  seen[u] = 1;
  while(!seen[togr[u]]) {
    u = togr[u];
    seen[u] = 1;
  }
  // dp
  dfs(u, u);
  return min(dpst[u], dpew[u] + 1);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>N;
  if(N%2) {
    cout<<"-1\n";
    return 0;
  }
  unordered_map<string, int> id;
  vector<string> pts;
  for(int i=0; i<N; ++i) {
    string a,b;
    cin>>a>>b;
    id[a] = i;
    pts.emplace_back(b);
  }
  for(int i=0; i<N; ++i) {
    togr[i] = id[pts[i]];
    fromgr[id[pts[i]]].emplace_back(i);
  }

  int ans = 0;
  for(int i=0; i<N; ++i) {
    if(vis[i]) continue;
    ans += solve(i);
  }
  // for(int i=0; i<N; ++i) cout<<dpst[i]<<' '<<dpew[i]<<'\n';
  cout<<ans<<'\n';
  return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Incorrect 1 ms 3676 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 19144 KB Output is correct
2 Correct 81 ms 21760 KB Output is correct
3 Correct 64 ms 19896 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 71 ms 27172 KB Output is correct
6 Correct 68 ms 18512 KB Output is correct
7 Correct 58 ms 18368 KB Output is correct
8 Correct 68 ms 18884 KB Output is correct
9 Correct 51 ms 18120 KB Output is correct
10 Correct 39 ms 17776 KB Output is correct
11 Correct 1 ms 3672 KB Output is correct
12 Correct 1 ms 3676 KB Output is correct
13 Correct 1 ms 3676 KB Output is correct
14 Correct 2 ms 3912 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Incorrect 1 ms 3676 KB Output isn't correct
9 Halted 0 ms 0 KB -