oj.uz

Submission #105786

# Submission time Handle Problem Language Result Execution time Memory
105786 2019-04-14T21:12:43 Z imaxblue Duathlon (APIO18_duathlon) C++17
0 / 100
 196 ms 38028 KB 
#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];
      dp[1][N] += dp[0][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 - 2);
    }
  }
  if (N <= 100000){
    ans += (sz)*(sz-1)*(sz-2)/2;
    dp[0][N] += (sz-1);
    dp[1][N] += (sz-1)*(sz-2);
  }
  //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;
}

Compilation message

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:87:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:87: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:127:7:
   fox(l, comp.size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:127: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:128:9:
     fox(l2, comp[l].size()){
         ~~~~~~~~~~~~~~~~~~        
count_triplets.cpp:128:5: note: in expansion of macro 'fox'
     fox(l2, comp[l].size()){
     ^~~
count_triplets.cpp:115: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:117: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:65:28: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
       ans += dp[0][nxt]*(sz-1)*(sz-2);
                         ~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 16 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 16 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 22084 KB Output is correct
2 Correct 105 ms 22132 KB Output is correct
3 Incorrect 119 ms 16748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 8 ms 7552 KB Output is correct
4 Correct 9 ms 7808 KB Output is correct
5 Correct 11 ms 7680 KB Output is correct
6 Correct 9 ms 7680 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 9 ms 7680 KB Output is correct
9 Correct 11 ms 7680 KB Output is correct
10 Incorrect 9 ms 7424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 25096 KB Output is correct
2 Correct 175 ms 26240 KB Output is correct
3 Correct 174 ms 26248 KB Output is correct
4 Correct 183 ms 26264 KB Output is correct
5 Correct 137 ms 26212 KB Output is correct
6 Correct 166 ms 38028 KB Output is correct
7 Correct 167 ms 33900 KB Output is correct
8 Correct 189 ms 31908 KB Output is correct
9 Correct 196 ms 30180 KB Output is correct
10 Incorrect 129 ms 21164 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 9 ms 7596 KB Output is correct
3 Incorrect 9 ms 7552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 25020 KB Output is correct
2 Correct 192 ms 26400 KB Output is correct
3 Incorrect 184 ms 24736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 16 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 16 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -