oj.uz

Submission #105793

# Submission time Handle Problem Language Result Execution time Memory
105793 2019-04-14T22:06:46 Z imaxblue Duathlon (APIO18_duathlon) C++17
31 / 100
 224 ms 37024 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], u[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){
  u[N]=1;
  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;
      crit[N] = 1;
    }
    low[N] = min(low[N], current[nxt]?ord[nxt]:low[nxt]);
  }
  current[N] = 0;
  //cout << N << ' ' << ord[N] << ' ' << low[N] << endl;
}
void run(int start){
  fox(l, comp.size()){
    dp[0][l] = dp[1][l]=0;
    w[l].clear();
  }
  comp.clear();
  dfs(start, -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(start + 100000, -1);

}
int32_t main(){
  scanf("%i%i", &n, &m);
  fox(l, m){
    scanf("%i%i", &x, &y);
    v[x].pb(y);
    v[y].pb(x);
  }
  fox1(l, n){
    if (!u[l]) run(l);
  }
  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:88:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:88:3: note: in expansion of macro 'fox'
   fox(l, v[N].size()){
   ^~~
count_triplets.cpp: In function 'void run(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:115:7:
   fox(l, comp.size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:115: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: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: In function 'int32_t main()':
count_triplets.cpp:141: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:143: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 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 17 ms 7424 KB Output is correct
6 Correct 9 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 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 17 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 22184 KB Output is correct
2 Correct 107 ms 22240 KB Output is correct
3 Correct 224 ms 28008 KB Output is correct
4 Correct 147 ms 25492 KB Output is correct
5 Correct 165 ms 24144 KB Output is correct
6 Correct 191 ms 28252 KB Output is correct
7 Correct 202 ms 22068 KB Output is correct
8 Correct 144 ms 23720 KB Output is correct
9 Correct 126 ms 19380 KB Output is correct
10 Correct 143 ms 20524 KB Output is correct
11 Correct 107 ms 15632 KB Output is correct
12 Correct 109 ms 15480 KB Output is correct
13 Correct 92 ms 15608 KB Output is correct
14 Correct 123 ms 15352 KB Output is correct
15 Correct 75 ms 14708 KB Output is correct
16 Correct 77 ms 14580 KB Output is correct
17 Correct 13 ms 9852 KB Output is correct
18 Correct 14 ms 9976 KB Output is correct
19 Correct 14 ms 9676 KB Output is correct
20 Correct 14 ms 9724 KB Output is correct
21 Correct 14 ms 9596 KB Output is correct
22 Correct 11 ms 9596 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Correct 10 ms 7552 KB Output is correct
4 Correct 10 ms 7808 KB Output is correct
5 Correct 9 ms 7680 KB Output is correct
6 Correct 10 ms 7680 KB Output is correct
7 Correct 10 ms 7680 KB Output is correct
8 Correct 10 ms 7680 KB Output is correct
9 Correct 12 ms 7680 KB Output is correct
10 Correct 14 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 9 ms 7552 KB Output is correct
13 Correct 9 ms 7552 KB Output is correct
14 Correct 9 ms 7456 KB Output is correct
15 Correct 8 ms 7424 KB Output is correct
16 Correct 8 ms 7552 KB Output is correct
17 Correct 9 ms 7552 KB Output is correct
18 Correct 8 ms 7552 KB Output is correct
19 Correct 9 ms 7552 KB Output is correct
20 Correct 8 ms 7552 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 25152 KB Output is correct
2 Correct 187 ms 25120 KB Output is correct
3 Correct 157 ms 25212 KB Output is correct
4 Correct 166 ms 25124 KB Output is correct
5 Correct 179 ms 25156 KB Output is correct
6 Correct 220 ms 37024 KB Output is correct
7 Correct 219 ms 32676 KB Output is correct
8 Correct 203 ms 30800 KB Output is correct
9 Correct 179 ms 28960 KB Output is correct
10 Correct 154 ms 20272 KB Output is correct
11 Correct 166 ms 23716 KB Output is correct
12 Correct 175 ms 18220 KB Output is correct
13 Correct 176 ms 17492 KB Output is correct
14 Correct 122 ms 14860 KB Output is correct
15 Correct 105 ms 14824 KB Output is correct
16 Correct 72 ms 13812 KB Output is correct
17 Correct 109 ms 22628 KB Output is correct
18 Correct 119 ms 22556 KB Output is correct
19 Correct 92 ms 22684 KB Output is correct
20 Correct 103 ms 22568 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 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 192 ms 25152 KB Output is correct
2 Correct 168 ms 25360 KB Output is correct
3 Incorrect 156 ms 23496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 17 ms 7424 KB Output is correct
6 Correct 9 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 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 17 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Incorrect 9 ms 7424 KB Output isn't correct
8 Halted 0 ms 0 KB -