제출 #76364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76364		Simphoni	철인 이종 경기 (APIO18_duathlon)	C++14	100 / 100	158 ms	102848 KiB

count_triplets

#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>
using namespace std;

typedef long long LL;
const int N = 1e5 + 50;

struct edge {
  int nxt, to;
} E[N << 2], G[N << 4];
int fir[N], lst[N << 1], cnt = 1;

int n, m;
int dfn[N], lo[N], top, clo, bcc, sz[N << 1];
pair <int, int> sta[N];
bool vis[N << 1];
LL ans = 0;

inline void addedge(int x, int y, edge *e = E, int *f = fir) {
  e[++ cnt] = (edge) { f[x], y }; f[x] = cnt;
}

inline int Dfs(int x, int f) {
  int low = lo[x] = dfn[x] = ++ clo, o;
  for (int i = fir[x]; i; i = E[i].nxt)
    if (E[i].to != f) {
      if (!dfn[E[i].to]) {
        sta[++ top] = make_pair(x, E[i].to);
        o = Dfs(E[i].to, x);
        low = min(low, o);
        if (o < dfn[x]) continue;
        bcc ++;
        set <int> tmp;
        while (top) {
          if (!tmp.count(sta[top].first)) {
            addedge(bcc, sta[top].first, G, lst);
            addedge(sta[top].first, bcc, G, lst);
            tmp.insert(sta[top].first);
          }
          if (!tmp.count(sta[top].second)) {
            addedge(bcc, sta[top].second, G, lst);
            addedge(sta[top].second, bcc, G, lst);
            tmp.insert(sta[top].second);
          }
          top --; 
          if (sta[top + 1] == make_pair(x, E[i].to)) break;
        }
        sz[bcc] = tmp.size();
      }
      else low = min(low, lo[E[i].to]);
    }
  return lo[x] = low;
}

inline pair <int, LL> Dfs1(int x) {
  vis[x] = 1;
  pair <int, LL> res = make_pair(0, 0), tmp;
  for (int i = lst[x]; i; i = G[i].nxt)
    if (!vis[G[i].to]) {
      tmp = Dfs1(G[i].to);
      ans += res.second * tmp.first + tmp.second * res.first + (LL)(x <= n ? -1 : sz[x]) * res.first * tmp.first;
      res.first += tmp.first;
      res.second += tmp.second;
    }
  res.second += (LL) res.first * (x <= n ? -1 : sz[x]);
  if (x <= n) ans += res.second, res.first ++, res.second --;
  return res;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, x, y; i <= m; i ++) {
    scanf("%d%d", &x, &y);
    addedge(x, y); addedge(y, x);
  }
  bcc = n;
  for (int i = 1; i <= n; i ++) if (!dfn[i]) Dfs(i, 0);
  for (int i = 1; i <= n; i ++) if (!vis[i]) Dfs1(i);
  printf("%lld\n", ans * 2);
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10