oj.uz

Submission #105792

# Submission time Handle Problem Language Result Execution time Memory
105792 2019-04-14T22:03:04 Z imaxblue Duathlon (APIO18_duathlon) C++17
0 / 100
 250 ms 36880 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;
      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;
}
void run(int start){
  fox(l, comp.size()) 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(100001, -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:116:7:
   fox(l, comp.size()) w[l].clear();
       ~~~~~~~~~~~~~~              
count_triplets.cpp:116:3: note: in expansion of macro 'fox'
   fox(l, comp.size()) w[l].clear();
   ^~~
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:124:7:
   fox(l, comp.size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:124: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:125:9:
     fox(l2, comp[l].size()){
         ~~~~~~~~~~~~~~~~~~        
count_triplets.cpp:125:5: note: in expansion of macro 'fox'
     fox(l2, comp[l].size()){
     ^~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:139: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:141: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 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 22148 KB Output is correct
2 Correct 117 ms 23236 KB Output is correct
3 Incorrect 199 ms 30504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 25176 KB Output is correct
2 Correct 154 ms 25300 KB Output is correct
3 Correct 153 ms 25224 KB Output is correct
4 Correct 167 ms 25044 KB Output is correct
5 Correct 228 ms 25120 KB Output is correct
6 Correct 250 ms 36880 KB Output is correct
7 Correct 229 ms 32672 KB Output is correct
8 Correct 228 ms 30756 KB Output is correct
9 Correct 180 ms 29088 KB Output is correct
10 Incorrect 171 ms 20216 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7552 KB Output is correct
2 Correct 8 ms 7552 KB Output is correct
3 Incorrect 8 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 155 ms 25092 KB Output is correct
2 Correct 182 ms 25356 KB Output is correct
3 Incorrect 250 ms 23456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -