oj.uz

Submission #387916

# Submission time Handle Problem Language Result Execution time Memory
387916 2021-04-09T12:25:54 Z kimbj0709 Love Polygon (BOI18_polygon) C++14
54 / 100
 743 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<set<int> > adj(maxn);
vector<vector<int> > fadj(maxn);
vector<int> canuse(maxn,1);
map<string,int> map1;
int currcount = 0;
int ans = 0;
void dfs1(int node,int parent){
  for(auto k:fadj[node]){
    if(k!=parent&&canuse[k]==1){
      dfs1(k,node);
    }
  }
  if(canuse[node]==0){

  }
  else if(parent!=-1&&canuse[parent]==1){
    canuse[node] = 0;
    canuse[parent] = 0;
    ans++;
  }
  else{
    ans++;
    canuse[node] = 0;
  }
}
void dfs(int node){
  canuse[node] = 0;
  currcount++;
  for(auto k:fadj[node]){
    if(canuse[k]==1){
      dfs(k);
    }
  }
}
int mapper(string a){
  if(map1.count(a)==0){
    map1.insert({a,map1.size()});
  }
  return map1[a];
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n;
  string input1,input2;
  int a,b;
  cin >> n;
  if(n%2==1){
    cout << -1;
    return 0;
  }
  vector<int> indeg(maxn,0);
  for(int i=0;i<n;i++){
    cin >> input1 >> input2;
    a = mapper(input1);
    b = mapper(input2);
    if(a!=b){
      fadj[a].push_back(b);
      fadj[b].push_back(a);
      adj[a].insert(b);
      indeg[b]++;
    }
  }
  for(int i=0;i<n;i++){
    for(auto k:adj[i]){
      if(adj[k].find(i)!=adj[k].end()){
        canuse[i] = 0;
        canuse[k] = 0;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(canuse[i]==1&&indeg[i]==0){
      dfs1(i,-1);
    }
  }
  for(int i=0;i<n;i++){
    if(canuse[i]==1){
      dfs(i);
      if(currcount%2==1){
        ans += currcount/2+1;
      }
      else{
        ans += currcount/2;
      }
      currcount = 0;
    }
  }
  cout << ans;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 8908 KB Output is correct
3 Correct 6 ms 8908 KB Output is correct
4 Runtime error 743 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8908 KB Output is correct
2 Correct 6 ms 8932 KB Output is correct
3 Correct 6 ms 8832 KB Output is correct
4 Correct 440 ms 29336 KB Output is correct
5 Correct 398 ms 26564 KB Output is correct
6 Correct 484 ms 29848 KB Output is correct
7 Correct 6 ms 8140 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 27016 KB Output is correct
2 Correct 416 ms 27968 KB Output is correct
3 Correct 254 ms 18892 KB Output is correct
4 Correct 6 ms 8180 KB Output is correct
5 Correct 454 ms 30972 KB Output is correct
6 Correct 385 ms 27332 KB Output is correct
7 Correct 408 ms 27396 KB Output is correct
8 Correct 322 ms 23632 KB Output is correct
9 Correct 363 ms 27484 KB Output is correct
10 Correct 261 ms 27520 KB Output is correct
11 Correct 6 ms 8908 KB Output is correct
12 Correct 6 ms 8916 KB Output is correct
13 Correct 6 ms 8920 KB Output is correct
14 Correct 6 ms 8908 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 8908 KB Output is correct
3 Correct 6 ms 8908 KB Output is correct
4 Runtime error 743 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -