제출 #105785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105785		imaxblue	철인 이종 경기 (APIO18_duathlon)	C++17	0 / 100	181 ms	26264 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846

int n, m, x, y, c, c2;
vector<vector<int> > comp;
vector<int> curr;
vector<int> v[100005];
vector<int> w[200005];
int ord[100005], low[100005];
ll dp[2][200005];
vector<int> last;
bool crit[100005], current[100005];
ll ans;
void dfs2(int N, int P){
  //dont count the articulation point twice
  //counts all paths up to current component
  //counts all paths at an articulation point below it that does not end on it
  ll sz;
  if (N <= 100000){
      sz = comp[N].size();
  }
  fox(l, w[N].size()){
    int nxt = w[N][l];
    if (nxt == P) continue;
    dfs2(nxt, N);
    if (N > 100000){
      //articulation
      ans += dp[1][N]*dp[0][nxt] + dp[0][N]*dp[1][nxt];
      dp[0][N] += dp[0][nxt];
      dp[1][N] += dp[1][nxt];
    } else {
      //component
      ans += dp[0][nxt]*(sz-1)*(sz-2);
      ans += dp[1][nxt]*(sz-1);
      ans += dp[0][nxt]*dp[1][N];
      ans += dp[1][nxt]*dp[0][N];
      dp[0][N] += dp[0][nxt];
      dp[1][N] += dp[1][nxt];
      dp[1][N] += dp[0][nxt] * (sz - 1);
    }
  }
  if (N <= 100000){
    ans += (sz)*(sz-1)*(sz-2)/2;
    dp[0][N] += (sz-1);
    dp[1][N] += (sz-1)*(sz-1);
  }
  //cout << N << ' ' << sz << ' ' << dp[0][N] << ' ' << dp[1][N] << ' ' << ans << endl;
}
bool spec;
void dfs(int N, int P){
  if (ord[N]) return;
  last.pb(N);
  current[N] = 1;
  low[N] = ord[N] = ++c;
  fox(l, v[N].size()){
    int nxt = v[N][l];
    if (nxt == P) continue;
    if (ord[nxt]){
      low[N] = min(low[N], ord[nxt]);
      continue;
    }
    dfs(nxt, N);
    if (low[nxt] >= ord[N]){
      int top = -1;
      curr.clear();
      while(1){
        top = last.back();
        curr.pb(top);
        if (top == N) break;
        last.pop_back();
      }
      comp.pb(curr);
      //cout << "*" << N << ' ' << curr.size() << endl;
      if (N == 1 && crit[N]) spec = 1;
      crit[N] = 1;
    }
    low[N] = min(low[N], current[nxt]?ord[nxt]:low[nxt]);
  }
  current[N] = 0;
  //cout << N << ' ' << ord[N] << ' ' << low[N] << endl;
}
int32_t main(){
  scanf("%i%i", &n, &m);
  fox(l, m){
    scanf("%i%i", &x, &y);
    v[x].pb(y);
    v[y].pb(x);
  }
  dfs(1, -1);
  //crit[1] = spec;
  //fox1(l, n) if (crit[l]) c2++;
  //printf("%i\n", c2);
  //fox1(l, n) if (crit[l]) printf("%i ", l); printf("\n");
  //return 0;
  fox(l, comp.size()){
    fox(l2, comp[l].size()){
      //cout << comp[l][l2] << ' ';
      if (crit[comp[l][l2]]){
        //cout << l << ' ' << comp[l][l2] << endl;
        w[l].pb(comp[l][l2] + 100000);
        w[comp[l][l2]+100000].pb(l);
      }
    }
    //cout << endl;
  }
  dfs2(100001, -1);
  cout << ans*2;
  return 0;
}

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

count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:53:7:
   fox(l, w[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:53:3: note: in expansion of macro 'fox'
   fox(l, w[N].size()){
   ^~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:86:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:86:3: note: in expansion of macro 'fox'
   fox(l, v[N].size()){
   ^~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:126:7:
   fox(l, comp.size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:126:3: note: in expansion of macro 'fox'
   fox(l, comp.size()){
   ^~~
count_triplets.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
count_triplets.cpp:127:9:
     fox(l2, comp[l].size()){
         ~~~~~~~~~~~~~~~~~~        
count_triplets.cpp:127:5: note: in expansion of macro 'fox'
     fox(l2, comp[l].size()){
     ^~~
count_triplets.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i%i", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:64:28: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
       ans += dp[0][nxt]*(sz-1)*(sz-2);
                         ~~~^~~

• Subtask 1: 0 / 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