oj.uz

답안 #771846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771846 2023-07-03T10:28:23 Z Sam_a17 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 294 ms 71220 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], i});
        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;
  }


  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:258:16: warning: unused variable 'j' [-Wunused-variable]
  258 |       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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38220 KB Output is correct
2 Correct 20 ms 38228 KB Output is correct
3 Correct 20 ms 38216 KB Output is correct
4 Correct 19 ms 38332 KB Output is correct
5 Correct 18 ms 38224 KB Output is correct
6 Correct 18 ms 38308 KB Output is correct
7 Correct 19 ms 38308 KB Output is correct
8 Incorrect 18 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38220 KB Output is correct
2 Correct 20 ms 38228 KB Output is correct
3 Correct 20 ms 38216 KB Output is correct
4 Correct 19 ms 38332 KB Output is correct
5 Correct 18 ms 38224 KB Output is correct
6 Correct 18 ms 38308 KB Output is correct
7 Correct 19 ms 38308 KB Output is correct
8 Incorrect 18 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 54136 KB Output is correct
2 Correct 69 ms 54180 KB Output is correct
3 Correct 175 ms 60652 KB Output is correct
4 Correct 129 ms 57620 KB Output is correct
5 Correct 142 ms 55628 KB Output is correct
6 Correct 178 ms 60524 KB Output is correct
7 Correct 201 ms 59272 KB Output is correct
8 Correct 174 ms 59676 KB Output is correct
9 Correct 191 ms 58084 KB Output is correct
10 Correct 163 ms 56752 KB Output is correct
11 Correct 126 ms 53964 KB Output is correct
12 Correct 178 ms 53928 KB Output is correct
13 Correct 119 ms 53868 KB Output is correct
14 Correct 140 ms 53532 KB Output is correct
15 Correct 98 ms 53300 KB Output is correct
16 Correct 107 ms 52728 KB Output is correct
17 Correct 28 ms 44292 KB Output is correct
18 Correct 28 ms 44328 KB Output is correct
19 Correct 27 ms 44212 KB Output is correct
20 Correct 28 ms 44092 KB Output is correct
21 Correct 27 ms 44012 KB Output is correct
22 Correct 28 ms 44048 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38576 KB Output is correct
2 Correct 20 ms 38528 KB Output is correct
3 Correct 21 ms 38540 KB Output is correct
4 Correct 24 ms 38676 KB Output is correct
5 Correct 20 ms 38556 KB Output is correct
6 Correct 19 ms 38612 KB Output is correct
7 Correct 19 ms 38572 KB Output is correct
8 Correct 18 ms 38548 KB Output is correct
9 Correct 19 ms 38572 KB Output is correct
10 Correct 20 ms 38484 KB Output is correct
11 Correct 20 ms 38612 KB Output is correct
12 Correct 20 ms 38544 KB Output is correct
13 Correct 20 ms 38552 KB Output is correct
14 Correct 19 ms 38484 KB Output is correct
15 Correct 22 ms 38484 KB Output is correct
16 Correct 19 ms 38464 KB Output is correct
17 Correct 23 ms 38620 KB Output is correct
18 Correct 19 ms 38632 KB Output is correct
19 Correct 20 ms 38636 KB Output is correct
20 Correct 20 ms 38508 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 64292 KB Output is correct
2 Correct 247 ms 64296 KB Output is correct
3 Correct 227 ms 64248 KB Output is correct
4 Correct 241 ms 64332 KB Output is correct
5 Correct 255 ms 64240 KB Output is correct
6 Correct 294 ms 71220 KB Output is correct
7 Correct 285 ms 69196 KB Output is correct
8 Correct 237 ms 67788 KB Output is correct
9 Correct 233 ms 66560 KB Output is correct
10 Correct 282 ms 64416 KB Output is correct
11 Correct 225 ms 64240 KB Output is correct
12 Correct 234 ms 64320 KB Output is correct
13 Correct 242 ms 64296 KB Output is correct
14 Correct 210 ms 62832 KB Output is correct
15 Correct 238 ms 61176 KB Output is correct
16 Correct 117 ms 55936 KB Output is correct
17 Correct 183 ms 65696 KB Output is correct
18 Correct 177 ms 65304 KB Output is correct
19 Correct 177 ms 64692 KB Output is correct
20 Correct 180 ms 64840 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 38568 KB Output is correct
2 Correct 21 ms 38556 KB Output is correct
3 Incorrect 20 ms 38528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 64076 KB Output is correct
2 Correct 229 ms 64052 KB Output is correct
3 Incorrect 199 ms 58240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38220 KB Output is correct
2 Correct 20 ms 38228 KB Output is correct
3 Correct 20 ms 38216 KB Output is correct
4 Correct 19 ms 38332 KB Output is correct
5 Correct 18 ms 38224 KB Output is correct
6 Correct 18 ms 38308 KB Output is correct
7 Correct 19 ms 38308 KB Output is correct
8 Incorrect 18 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 38220 KB Output is correct
2 Correct 20 ms 38228 KB Output is correct
3 Correct 20 ms 38216 KB Output is correct
4 Correct 19 ms 38332 KB Output is correct
5 Correct 18 ms 38224 KB Output is correct
6 Correct 18 ms 38308 KB Output is correct
7 Correct 19 ms 38308 KB Output is correct
8 Incorrect 18 ms 38228 KB Output isn't correct
9 Halted 0 ms 0 KB -