oj.uz

Submission #771851

# Submission time Handle Problem Language Result Execution time Memory
771851 2023-07-03T10:32:10 Z Sam_a17 Duathlon (APIO18_duathlon) C++17
66 / 100
 250 ms 70996 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 popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
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;}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
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(vector <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> void print(Tree <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> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// 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 == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  } else if(str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}

const int N = 4e5 + 10;
vector<int> adj[N], comps[N];
vector<pair<int, int>> adj2[N];
bool vis[N], vis2[N];
int dp[51][51][51];
long long n, m, ans, n2;
int st, tin[N], tout[N], timer;
int low[N], comp[N], sz_comp[N];

set<pair<int, int>> mp;
void IS_BRIDGE(int a, int b) {
  mp.insert({a, b});
  mp.insert({b, a});
}

void dfs(int v, int p = -1) {
  vis[v] = true;
  tin[v] = low[v] = timer++;
  for (int to : adj[v]) {
      if (to == p) continue;
      if (vis[to]) {
          low[v] = min(low[v], tin[to]);
      } else {
          dfs(to, v);
          low[v] = min(low[v], low[to]);
          if (low[to] > tin[v]) {
              IS_BRIDGE(v, to);
          }
      }
  }
}

void dfs_gen(int node) {
  vis[node] = true;
  comps[st].push_back(node);
  for(auto i: adj[node]) {
    pair<int, int> edge = {i, node};

    if(mp.find(edge) != mp.end()) {
      if(comp[i]) {
        adj2[st].push_back({comp[i], node});
        adj2[comp[i]].push_back({st, i});
      }
      continue;
    }
    if(vis[i]) continue;

    comp[i] = st;
    sz_comp[i]++;
    dfs_gen(i);
  }
}

long long sub[N];
void dfsik(int node, int parent) {
  vis[node] = true;
  sub[node] = sz(comps[node]);
  for(auto i: adj2[node]) {
    if(i.first == parent) continue;
    dfsik(i.first, node);
    sub[node] += sub[i.first];
  }
}

long long cur_al = 0, answ = 0;

vector<long long> have[N];
long long val[N];
vector<long long> whi;

void dfs1(int node, int parent) {
  vector<long long> child;
  if(sub[node] != cur_al) {
    long long vle = cur_al - sub[node];;
    for(auto i: adj2[node]) {
      if(i.first == parent) {
        have[i.second].push_back(vle);
        val[i.second] += vle;
        whi.push_back(i.second);
      }
    }
  }
  

  for(auto i: adj2[node]) {
    if(i.first == parent) continue;
    if(sz(have[i.second])) {
      have[i.second].push_back(sub[i.first]);
      val[i.second] += sub[i.first];
    } else {
      have[i.second].push_back(sub[i.first]);
      val[i.second] += sub[i.first];
      whi.push_back(i.second);
    }
  }

  long long sum = cur_al - sz(comps[node]);
  long long add = 0;
  for(auto i: whi) {
    long long bu = val[i];
    long long cmp = sz(comps[node]);
    answ += 2ll * (sum - bu) * bu * cmp;
    add += 2ll * (sum - bu) * bu * cmp;
    sum -= bu;
  }
  // dbg(node)
  // dbg(whi)


  if(sz(comps[node]) != 1) {
    for(auto i: whi) {
      long long bu = val[i];
      long long cmp = sz(comps[node]);
      answ += 2ll * bu * (cmp - 1);
      answ += 2ll * bu * (cmp - 1) * (cmp - 2); 
    }
  }

  for(auto i: whi) {
    sum = val[i];
    for(auto j: have[i]) {
      answ += 2 * (sum - j) * j;
      sum -= j;
    }

    val[i] = 0;
    have[i].clear();
  }
  whi.clear();
  
  for(auto i: adj2[node]) {
    if(i.first == parent) continue;
    dfs1(i.first, node);
  }
}

long long c_n(long long x) {
  if(x < 2) return 0;
  return x * (x - 1);
}

void solve_() {
  cin >> n >> m;

  for(int i = 1; i <= m; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  for(int i = 1; i <= n; i++) {
    low[i] = tin[i] = -1;
  }
  for(int i = 1; i <= n; i++) {
    if(vis[i]) continue;
    dfs(i, 0);
  }

  memset(vis, 0, sizeof(vis));

  for(int i = 1; i <= n; i++) {
    if(!vis[i]) {
      st = i;
      comp[i] = st;
      sz_comp[i]++;
      dfs_gen(i);
    }
  }

  for(int i = 1; i <= n; i++) {
    sort(all(adj2[i]));
    uniq(adj2[i]);
  }

  for(int i = 1; i <= n; i++) {
    if(comp[i] == i) {
      for(auto j: comps[i]) {
        ans += c_n(sz(comps[i]) - 1);
      }
    }
  }


  memset(vis, 0, sizeof(vis));

  for(int i = 1; i <= n; i++) {
    if(vis[comp[i]]) continue;
    dfsik(i, 0);

    cur_al = sub[i];
    dfs1(i, 0);
  }
  cout << ans + answ << '\n';
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

count_triplets.cpp: In function 'void solve_()':
count_triplets.cpp:260:16: warning: unused variable 'j' [-Wunused-variable]
  260 |       for(auto j: comps[i]) {
      |                ^
count_triplets.cpp: In function 'void setIO(std::string)':
count_triplets.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38228 KB Output is correct
2 Correct 18 ms 38228 KB Output is correct
3 Correct 18 ms 38300 KB Output is correct
4 Correct 17 ms 38240 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 18 ms 38228 KB Output is correct
7 Correct 18 ms 38228 KB Output is correct
8 Incorrect 17 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38228 KB Output is correct
2 Correct 18 ms 38228 KB Output is correct
3 Correct 18 ms 38300 KB Output is correct
4 Correct 17 ms 38240 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 18 ms 38228 KB Output is correct
7 Correct 18 ms 38228 KB Output is correct
8 Incorrect 17 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 52936 KB Output is correct
2 Correct 61 ms 52908 KB Output is correct
3 Correct 152 ms 59920 KB Output is correct
4 Correct 125 ms 56580 KB Output is correct
5 Correct 129 ms 54836 KB Output is correct
6 Correct 181 ms 59968 KB Output is correct
7 Correct 177 ms 58600 KB Output is correct
8 Correct 180 ms 59116 KB Output is correct
9 Correct 170 ms 57464 KB Output is correct
10 Correct 167 ms 56160 KB Output is correct
11 Correct 125 ms 53580 KB Output is correct
12 Correct 130 ms 53540 KB Output is correct
13 Correct 113 ms 53716 KB Output is correct
14 Correct 124 ms 53424 KB Output is correct
15 Correct 99 ms 53516 KB Output is correct
16 Correct 96 ms 52828 KB Output is correct
17 Correct 29 ms 44516 KB Output is correct
18 Correct 29 ms 44516 KB Output is correct
19 Correct 26 ms 44388 KB Output is correct
20 Correct 25 ms 44460 KB Output is correct
21 Correct 26 ms 44244 KB Output is correct
22 Correct 26 ms 44220 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38612 KB Output is correct
2 Correct 19 ms 38560 KB Output is correct
3 Correct 19 ms 38564 KB Output is correct
4 Correct 19 ms 38612 KB Output is correct
5 Correct 19 ms 38616 KB Output is correct
6 Correct 18 ms 38560 KB Output is correct
7 Correct 20 ms 38604 KB Output is correct
8 Correct 19 ms 38636 KB Output is correct
9 Correct 19 ms 38612 KB Output is correct
10 Correct 19 ms 38612 KB Output is correct
11 Correct 21 ms 38508 KB Output is correct
12 Correct 19 ms 38484 KB Output is correct
13 Correct 19 ms 38620 KB Output is correct
14 Correct 18 ms 38596 KB Output is correct
15 Correct 22 ms 38468 KB Output is correct
16 Correct 19 ms 38484 KB Output is correct
17 Correct 19 ms 38612 KB Output is correct
18 Correct 19 ms 38612 KB Output is correct
19 Correct 19 ms 38516 KB Output is correct
20 Correct 18 ms 38612 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 64676 KB Output is correct
2 Correct 232 ms 64624 KB Output is correct
3 Correct 231 ms 64588 KB Output is correct
4 Correct 230 ms 64712 KB Output is correct
5 Correct 230 ms 64652 KB Output is correct
6 Correct 242 ms 70996 KB Output is correct
7 Correct 241 ms 69188 KB Output is correct
8 Correct 250 ms 67964 KB Output is correct
9 Correct 237 ms 66756 KB Output is correct
10 Correct 230 ms 64616 KB Output is correct
11 Correct 242 ms 64716 KB Output is correct
12 Correct 232 ms 64592 KB Output is correct
13 Correct 244 ms 64580 KB Output is correct
14 Correct 218 ms 63240 KB Output is correct
15 Correct 210 ms 61624 KB Output is correct
16 Correct 116 ms 56428 KB Output is correct
17 Correct 163 ms 65256 KB Output is correct
18 Correct 180 ms 65244 KB Output is correct
19 Correct 173 ms 65260 KB Output is correct
20 Correct 179 ms 65300 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38612 KB Output is correct
2 Correct 19 ms 38544 KB Output is correct
3 Correct 19 ms 38484 KB Output is correct
4 Correct 20 ms 38484 KB Output is correct
5 Correct 18 ms 38380 KB Output is correct
6 Correct 19 ms 38456 KB Output is correct
7 Correct 19 ms 38420 KB Output is correct
8 Correct 19 ms 38356 KB Output is correct
9 Correct 19 ms 38356 KB Output is correct
10 Correct 18 ms 38388 KB Output is correct
11 Correct 18 ms 38324 KB Output is correct
12 Correct 19 ms 38532 KB Output is correct
13 Correct 18 ms 38484 KB Output is correct
14 Correct 19 ms 38484 KB Output is correct
15 Correct 19 ms 38448 KB Output is correct
16 Correct 19 ms 38484 KB Output is correct
17 Correct 20 ms 38636 KB Output is correct
18 Correct 19 ms 38484 KB Output is correct
19 Correct 19 ms 38432 KB Output is correct
20 Correct 19 ms 38448 KB Output is correct
21 Correct 20 ms 38452 KB Output is correct
22 Correct 19 ms 38560 KB Output is correct
23 Correct 19 ms 38484 KB Output is correct
24 Correct 25 ms 38480 KB Output is correct
25 Correct 19 ms 38444 KB Output is correct
26 Correct 19 ms 38336 KB Output is correct
27 Correct 19 ms 38348 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 64808 KB Output is correct
2 Correct 239 ms 64408 KB Output is correct
3 Correct 188 ms 57908 KB Output is correct
4 Correct 153 ms 54384 KB Output is correct
5 Correct 120 ms 50548 KB Output is correct
6 Correct 103 ms 49136 KB Output is correct
7 Correct 100 ms 48528 KB Output is correct
8 Correct 88 ms 47740 KB Output is correct
9 Correct 84 ms 47344 KB Output is correct
10 Correct 80 ms 47172 KB Output is correct
11 Correct 89 ms 46544 KB Output is correct
12 Correct 68 ms 45980 KB Output is correct
13 Correct 66 ms 45856 KB Output is correct
14 Correct 60 ms 46924 KB Output is correct
15 Correct 211 ms 63840 KB Output is correct
16 Correct 192 ms 62284 KB Output is correct
17 Correct 192 ms 59536 KB Output is correct
18 Correct 175 ms 58476 KB Output is correct
19 Correct 152 ms 54448 KB Output is correct
20 Correct 148 ms 54408 KB Output is correct
21 Correct 154 ms 54328 KB Output is correct
22 Correct 128 ms 52768 KB Output is correct
23 Correct 111 ms 50892 KB Output is correct
24 Correct 178 ms 59540 KB Output is correct
25 Correct 179 ms 59688 KB Output is correct
26 Correct 156 ms 56272 KB Output is correct
27 Correct 161 ms 56328 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38228 KB Output is correct
2 Correct 18 ms 38228 KB Output is correct
3 Correct 18 ms 38300 KB Output is correct
4 Correct 17 ms 38240 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 18 ms 38228 KB Output is correct
7 Correct 18 ms 38228 KB Output is correct
8 Incorrect 17 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38228 KB Output is correct
2 Correct 18 ms 38228 KB Output is correct
3 Correct 18 ms 38300 KB Output is correct
4 Correct 17 ms 38240 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 18 ms 38228 KB Output is correct
7 Correct 18 ms 38228 KB Output is correct
8 Incorrect 17 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -