oj.uz

답안 #673888

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673888 2022-12-22T10:40:46 Z Sam_a17 관광지 (IZhO14_shymbulak) C++17
100 / 100
 104 ms 22172 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) x.clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T> void print(set <T> v);
template <class T> void print(vector <T> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T, class V> void print(pair <T, V> p);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque<T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(unordered_map<T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
 
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "" && str != "input") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
 
  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const long long inf = 1e15;
const int N = 2e5 + 10;
vector<int> adj[N];
 
pair<long long, long long> combine(pair<long long, long long> a, pair<long long, long long> b) {
  if(a.first == b.first) {
    a.second += b.second;
    return a;
  } else if(a.first > b.first) {
    return a;
  } else {
    return b;
  }
}
 
// for cycle
bool in_cycle[N];
int n, vis[N], p[N];
vector<int> cycle;
bool is_cycle = false;
 
void dfsCycle(int node, int parent) {
  vis[node] = 1, p[node] = parent;
  for(auto i: adj[node]) {
    if(i == parent) continue;
 
    if(vis[i] == 1) {
      int curr = node;
      while(curr != i) {
        cycle.push_back(curr);
        curr = p[curr];
      }
      cycle.push_back(curr);
      is_cycle = true;
      return;
    } else if(!vis[i]) {
      dfsCycle(i, node);
    }
 
    if(is_cycle) {
      return;
    }
  }
  vis[node] = 2;
}
 
// for trees
pair<long long, long long> dp[N];
pair<long long, long long> ans = {0, 0};
 
void dfs_depth(int node, int parent) {
  dp[node] = {0, 1};
 
  int cnt = 0;
  for(auto i: adj[node]) {
    if(i == parent || in_cycle[i]) continue;
    dfs_depth(i, node);
    cnt++;
    
 
    pair<long long, long long> sub = dp[i];
    sub.first++;
    if(cnt == 1) {
      dp[node] = sub;
    }
    else {
      pair<long long, long long> sub_x = {dp[node].first + dp[i].first + 1, dp[node].second * dp[i].second};
      dp[node] = combine(dp[node], sub);
      ans = combine(ans, sub_x);
    }
    ans = combine(ans, dp[node]);
  }
}
 
void solve_() {
  cin >> n;
 
  for(int i = 1; i <= n; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
 
  dfsCycle(1, 0);
 
  for(auto i: cycle) {
    in_cycle[i] = true;
  }
 
  for(auto i: cycle) {
    dfs_depth(i, 0);
  }
 
  int sz = sz(cycle);
  set<pair<long long, long long>> st;
  for(int i = 0; i < sz + sz / 2; i++) {
    if(i >= sz / 2) {
      pair<long long, long long> curr = {dp[cycle[i % sz]].first + i + st.rbegin()->first, 0};
      ans = combine(ans, curr);
      st.erase({dp[cycle[i - sz / 2]].first - (i - sz / 2), i - sz / 2});
    }
    st.insert({dp[cycle[i % sz]].first - i, i});
  }
 
  map<long long, long long> mp;
  for(int i = 0; i < sz + sz / 2; i++) {
    if(i >= sz / 2) {
      long long to_find = ans.first - (dp[cycle[i % sz]].first + i);
      ans.second += mp[to_find] * dp[cycle[i % sz]].second;
      mp[dp[cycle[i - sz / 2]].first - (i - sz / 2)] -= dp[cycle[i - sz / 2]].second;
    }
    mp[dp[cycle[i % sz]].first - i] += dp[cycle[i % sz]].second;
  }
 
  cout << ans.second << '\n';
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

shymbulak.cpp: In function 'void setIO(std::string)':
shymbulak.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5036 KB Output is correct
8 Correct 2 ms 5032 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5052 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5160 KB Output is correct
2 Correct 3 ms 5040 KB Output is correct
3 Correct 4 ms 5164 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5372 KB Output is correct
7 Correct 4 ms 5360 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 4 ms 5332 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 11092 KB Output is correct
2 Correct 44 ms 11836 KB Output is correct
3 Correct 58 ms 22172 KB Output is correct
4 Correct 31 ms 11908 KB Output is correct
5 Correct 31 ms 11764 KB Output is correct
6 Correct 104 ms 17136 KB Output is correct
7 Correct 71 ms 14632 KB Output is correct
8 Correct 60 ms 18464 KB Output is correct
9 Correct 62 ms 18060 KB Output is correct
10 Correct 67 ms 20148 KB Output is correct
11 Correct 62 ms 18476 KB Output is correct
12 Correct 71 ms 19096 KB Output is correct