oj.uz

Submission #105791

# Submission time Handle Problem Language Result Execution time Memory
105791 2019-04-14T22:00:46 Z imaxblue Duathlon (APIO18_duathlon) C++17
23 / 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], u[100005];
ll ans;
void dfs2(int N, int P){
  u[N] = 1;
  //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;
  }*/
  fox1(l, n){
    if (u[l]) continue;
    dfs2(l, -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:56:7:
   fox(l, w[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:56: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:90:7:
   fox(l, v[N].size()){
       ~~~~~~~~~~~~~~              
count_triplets.cpp:90:3: note: in expansion of macro 'fox'
   fox(l, v[N].size()){
   ^~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:118: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:120: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 985 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 985 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 1079 ms 219196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.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 8 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 10 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 9 ms 7452 KB Output is correct
12 Correct 10 ms 7424 KB Output is correct
13 Correct 12 ms 7424 KB Output is correct
14 Correct 11 ms 7424 KB Output is correct
15 Correct 11 ms 7424 KB Output is correct
16 Correct 9 ms 7424 KB Output is correct
17 Correct 11 ms 7424 KB Output is correct
18 Correct 11 ms 7424 KB Output is correct
19 Correct 10 ms 7424 KB Output is correct
20 Correct 10 ms 7424 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12792 KB Output is correct
2 Correct 85 ms 12852 KB Output is correct
3 Correct 72 ms 12792 KB Output is correct
4 Correct 101 ms 12792 KB Output is correct
5 Correct 83 ms 12792 KB Output is correct
6 Correct 85 ms 15608 KB Output is correct
7 Correct 92 ms 14944 KB Output is correct
8 Correct 82 ms 14456 KB Output is correct
9 Correct 118 ms 13860 KB Output is correct
10 Correct 91 ms 12896 KB Output is correct
11 Correct 89 ms 14012 KB Output is correct
12 Correct 101 ms 14044 KB Output is correct
13 Correct 91 ms 14072 KB Output is correct
14 Correct 82 ms 13816 KB Output is correct
15 Correct 70 ms 13304 KB Output is correct
16 Correct 57 ms 12128 KB Output is correct
17 Correct 54 ms 13420 KB Output is correct
18 Correct 54 ms 13416 KB Output is correct
19 Correct 49 ms 13408 KB Output is correct
20 Correct 60 ms 13544 KB Output is correct

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 891 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 84 ms 12816 KB Output is correct
2 Correct 87 ms 12828 KB Output is correct
3 Execution timed out 1138 ms 1001676 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 985 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 985 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -