제출 #60021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60021		dukati8	철인 이종 경기 (APIO18_duathlon)	C++14	5 / 100	238 ms	11288 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
bool flags[100000];
bool visits[100000];
vector<pair<int,int> > roads;
vector< vector<int> > close;
long long tot=0;
long long dp1[100000];
long long dp2[100000];
long long numfixed[100000];
bool dfs(int curr, int goal) {
  if (curr==goal) {flags[curr]=true; return true;}
  visits[curr]=true;
  for (auto a:close[curr]) {
    if (!visits[a]) {
      if (dfs(a,goal)) {flags[curr]=true; return true;}
    }
  }
  return false;
}
bool bfs(int start, int goal) {
  queue<int> order;
  order.push(start);
  int from[60];
  while (!order.empty()) {
    int now = order.front();
    order.pop();
    if (now==goal) {
      flags[now]=true;
      while (now!=start){
        now=from[now];
        flags[now]=true;
      }
      return true;
    }
    for (auto a:close[now]) {
      if (!visits[a]) {
        from[a]=now;
        order.push(a);
        visits[a]=true;
      }
    }
  }
  return false;
}
void dpupdate(int curr) {
  if (!flags[curr] && (close[curr].size()-numfixed[curr]==1 || close[curr].size()-numfixed[curr]==0)) {
    flags[curr]=true;
    long long tempcount=0;
    for (auto o:close[curr]) {
      if (flags[o]) {
        tot+=dp2[o];
        tempcount+=dp1[o];
      }
    }
    for (auto o: close[curr]) {
      if (!flags[o]) {
        dp1[o]+=dp1[curr];
        dp2[o]+=dp1[curr]+dp2[curr];
        numfixed[o]++;
        dpupdate(o);
      }
      else {
        tot+=dp1[o]*(tempcount-dp1[o]);
      }
    }
  }
}
int main() {
  int n,m;
  cin >>n >>m;
  if (n<=10) {
    close.assign(n,vector<int>());
    rep(i,0,m) {
      int u,v;
      cin >> u >> v;
      u--;v--;
      roads.push_back(make_pair(u,v));
      close[u].push_back(v);
      close[v].push_back(u);
    }
    int counter=0;
    rep(i,0,n) {
      rep (j,0,n) {
        rep (k,0,n) {
          if (i!=j && j!=k && i!=k) {
            //search route i to j and j to k, and if not works try other way instead.
            rep (x,0,n) {visits[x]=false; flags[x]=false;}
            if (bfs(i,j)) {
              rep (x,0,n) visits[x]=flags[x];
              if (bfs(j,k)) {counter++;}
              else {
                rep (x,0,n) {visits[x]=false; flags[x]=false;}
                if (bfs(j,k)) {
                  rep (x,0,n) visits[x]=flags[x];
                  if (bfs(j,i)) {counter++;}
                }
              }
            }
          }
        }
      }
    }
    cout << counter << endl;
  }
  else {
    //antag inga cykler
    close.assign(n,vector<int>());
    rep(i,0,m) {
      int u,v;
      cin >> u >> v;
      u--;v--;
      roads.push_back(make_pair(u,v));
      close[u].push_back(v);
      close[v].push_back(u);
    }

    rep (i,0,n) {dp1[i]=1; dp2[i]=0; numfixed[i]=0;}
    rep (i,0,n) {
      dpupdate(i);
    }
    cout << 2*tot << endl;
  }

}

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