oj.uz

Submission #105790

# Submission time Handle Problem Language Result Execution time Memory
105790 2019-04-14T21:59:18 Z imaxblue Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 1049600 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
#define int ll

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();
  }*/
  dp[0][N] = 1;
  fox(l, w[N].size()){
    int nxt = w[N][l];
    if (nxt == P) continue;
    dfs2(nxt, N);
    if (N > 100000 || 1){
      //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("%lli%lli", &n, &m);
  fox(l, m){
    scanf("%lli%lli", &x, &y);
    //x=l+1;
    //y=(l+1)%n+1;
    w[x].pb(y);
    w[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(1, -1);
  //dfs2(100001, -1);
  cout << ans*2;
  return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs2(long long int, long long 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:55:7:
   fox(l, w[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:55:3: note: in expansion of macro 'fox'
   fox(l, w[N].size()){
   ^~~
count_triplets.cpp: In function 'void dfs(long long int, long long 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:89:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:89:3: note: in expansion of macro 'fox'
   fox(l, v[N].size()){
   ^~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lli%lli", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lli%lli", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 235212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 ms 7552 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Incorrect 8 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 88 ms 12792 KB Output is correct
2 Correct 85 ms 12780 KB Output is correct
3 Correct 118 ms 12720 KB Output is correct
4 Correct 89 ms 12896 KB Output is correct
5 Correct 100 ms 12644 KB Output is correct
6 Correct 94 ms 15480 KB Output is correct
7 Correct 89 ms 14840 KB Output is correct
8 Correct 75 ms 14456 KB Output is correct
9 Correct 67 ms 13820 KB Output is correct
10 Incorrect 79 ms 12664 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 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Runtime error 930 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12664 KB Output is correct
2 Correct 72 ms 12536 KB Output is correct
3 Execution timed out 1073 ms 1049600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -