oj.uz

Submission #75367

# Submission time Handle Problem Language Result Execution time Memory
75367 2018-09-09T13:00:53 Z born2rule Duathlon (APIO18_duathlon) C++14
5 / 100
 1000 ms 22604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005;
vi v[N];
bool vis[N];
ll ans;
int n,m;
//for subtask 1,2
bool mark[N];
//for subtask 4,5
ll sumd[N]; int d[N],child[N];
bool checksub12()
{
  if(n>50) return false;
  function<void (int,int,int,vi&) > dfs = [&](int u,int s,int f,vi &tmp)->void
    {
      if(u==f)
	{
	  for(int x:tmp) mark[x]=true;
	  return;
	}
      vis[u]=true;
      tmp.pb(u);
      for(int v1:v[u]) if(!vis[v1]) dfs(v1,s,f,tmp);
      tmp.pop_back();
      vis[u]=false;
    };
  rep(i,1,n+1)
    rep(j,i+1,n+1)
    {
      rep(k,1,n+1) mark[k]=false;
      vi tmp;
      dfs(i,i,j,tmp);
      rep(k,1,n+1)
	if(k!=i && k!=j && mark[k]) ans+=2;
    }
  cout<<ans<<endl;
  return true;
}
bool checksub3()//make it correct
{
  bool sub3=true;
  rep(i,1,n+1) if(sz(v[i])>2) sub3=false;
  if(!sub3) return false;
  function<bool (int, vi&)> dfs = [&](int u,vi &tmp)->bool
    {
      vis[u]=true; tmp.pb(u);
      for(int v1:v[u]) if(!vis[v1]) dfs(v1,tmp);
    };
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      vi tmp;
      dfs(i,tmp);
      bool chain=false;
      for(int x:tmp) if(sz(v[x])==1) chain=true;
      int tot=sz(tmp);
      if(!chain) ans+=(ll)(tot-2)*(ll)tot*(tot-1);
      else
	rep(j,1,tot-1) ans+=((ll)j*(j+1))/2;
    }
  cout<<ans<<endl;
  return true;
}
bool checksub45()
{
  function<bool (int, int)> dfs = [&](int u,int par)->bool
    {
      child[u]=1;
      vis[u]=true;
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  if(vis[v1]) return false;
	  d[v1]=d[u]+1;
	  dfs(v1,u);
	  child[u]+=child[v1];
	}
      return true;
    };
  function<void (int, int)> dfs2 = [&](int u,int par)->void
    {
      vis[u]=true;
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  dfs2(v1,u);
	  sumd[u]+=sumd[v1];
	}
      for(int v1:v[u])
	{
	  if(v1==par) continue;
	  ans+=(ll)(child[u]-child[v1]-1)*(ll)sumd[v1];
	  ans+=(ll)child[v1]*(ll)(sumd[u]-sumd[v1]);
	  ans-=(ll)child[v1]*(child[u]-child[v1]-1)*(ll)(d[u]*2+1);
	}
      ans+=(ll)(sumd[u]-(ll)(child[u]-1)*(d[u]+1))*(ll)2;
      sumd[u]+=d[u];
    };
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      if(!dfs(i,-1)) return false;
    }
  memset(vis,false,sizeof(vis));
  rep(i,1,n+1)
    {
      if(vis[i]) continue;
      dfs2(i,-1);
    }
  cout<<ans<<endl;
  return true;
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  cin>>n>>m;
  rep(i,1,m+1)
    {
      int x,y;
      cin>>x>>y;
      v[x].pb(y); v[y].pb(x);
    }
  if(checksub12()) return 0;//brute
  if(checksub3()) return 0; //degree at most 2
  if(checksub45()) return 0;// a tree
  return 0 ;
}

Compilation message

count_triplets.cpp: In lambda function:
count_triplets.cpp:85:5: warning: no return statement in function returning non-void [-Wreturn-type]
     };
     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 4 ms 2920 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 4 ms 3044 KB Output is correct
7 Correct 5 ms 3044 KB Output is correct
8 Correct 5 ms 3160 KB Output is correct
9 Correct 19 ms 3160 KB Output is correct
10 Correct 325 ms 3184 KB Output is correct
11 Correct 5 ms 3184 KB Output is correct
12 Correct 5 ms 3184 KB Output is correct
13 Correct 4 ms 3184 KB Output is correct
14 Correct 4 ms 3184 KB Output is correct
15 Correct 5 ms 3184 KB Output is correct
16 Correct 4 ms 3184 KB Output is correct
17 Correct 5 ms 3184 KB Output is correct
18 Correct 5 ms 3184 KB Output is correct
19 Correct 4 ms 3184 KB Output is correct
20 Correct 4 ms 3184 KB Output is correct
21 Correct 5 ms 3184 KB Output is correct
22 Correct 4 ms 3184 KB Output is correct
23 Correct 5 ms 3184 KB Output is correct
24 Correct 4 ms 3184 KB Output is correct
25 Correct 5 ms 3184 KB Output is correct
26 Correct 4 ms 3184 KB Output is correct
27 Correct 5 ms 3184 KB Output is correct
28 Correct 4 ms 3184 KB Output is correct
29 Correct 4 ms 3184 KB Output is correct
30 Correct 4 ms 3184 KB Output is correct
31 Correct 4 ms 3184 KB Output is correct
32 Correct 4 ms 3184 KB Output is correct
33 Correct 4 ms 3184 KB Output is correct
34 Correct 4 ms 3184 KB Output is correct
35 Correct 4 ms 3184 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 4 ms 2920 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 4 ms 3044 KB Output is correct
7 Correct 5 ms 3044 KB Output is correct
8 Correct 5 ms 3160 KB Output is correct
9 Correct 19 ms 3160 KB Output is correct
10 Correct 325 ms 3184 KB Output is correct
11 Correct 5 ms 3184 KB Output is correct
12 Correct 5 ms 3184 KB Output is correct
13 Correct 4 ms 3184 KB Output is correct
14 Correct 4 ms 3184 KB Output is correct
15 Correct 5 ms 3184 KB Output is correct
16 Correct 4 ms 3184 KB Output is correct
17 Correct 5 ms 3184 KB Output is correct
18 Correct 5 ms 3184 KB Output is correct
19 Correct 4 ms 3184 KB Output is correct
20 Correct 4 ms 3184 KB Output is correct
21 Correct 5 ms 3184 KB Output is correct
22 Correct 4 ms 3184 KB Output is correct
23 Correct 5 ms 3184 KB Output is correct
24 Correct 4 ms 3184 KB Output is correct
25 Correct 5 ms 3184 KB Output is correct
26 Correct 4 ms 3184 KB Output is correct
27 Correct 5 ms 3184 KB Output is correct
28 Correct 4 ms 3184 KB Output is correct
29 Correct 4 ms 3184 KB Output is correct
30 Correct 4 ms 3184 KB Output is correct
31 Correct 4 ms 3184 KB Output is correct
32 Correct 4 ms 3184 KB Output is correct
33 Correct 4 ms 3184 KB Output is correct
34 Correct 4 ms 3184 KB Output is correct
35 Correct 4 ms 3184 KB Output is correct
36 Correct 4 ms 3184 KB Output is correct
37 Correct 4 ms 3184 KB Output is correct
38 Correct 27 ms 3188 KB Output is correct
39 Execution timed out 1073 ms 3192 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 14452 KB Output is correct
2 Correct 88 ms 15776 KB Output is correct
3 Incorrect 115 ms 15776 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15776 KB Output is correct
2 Correct 103 ms 15776 KB Output is correct
3 Correct 98 ms 15776 KB Output is correct
4 Correct 86 ms 16948 KB Output is correct
5 Correct 94 ms 18212 KB Output is correct
6 Incorrect 80 ms 22000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22000 KB Output is correct
2 Correct 89 ms 22000 KB Output is correct
3 Incorrect 77 ms 22604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 4 ms 2920 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 4 ms 3044 KB Output is correct
7 Correct 5 ms 3044 KB Output is correct
8 Correct 5 ms 3160 KB Output is correct
9 Correct 19 ms 3160 KB Output is correct
10 Correct 325 ms 3184 KB Output is correct
11 Correct 5 ms 3184 KB Output is correct
12 Correct 5 ms 3184 KB Output is correct
13 Correct 4 ms 3184 KB Output is correct
14 Correct 4 ms 3184 KB Output is correct
15 Correct 5 ms 3184 KB Output is correct
16 Correct 4 ms 3184 KB Output is correct
17 Correct 5 ms 3184 KB Output is correct
18 Correct 5 ms 3184 KB Output is correct
19 Correct 4 ms 3184 KB Output is correct
20 Correct 4 ms 3184 KB Output is correct
21 Correct 5 ms 3184 KB Output is correct
22 Correct 4 ms 3184 KB Output is correct
23 Correct 5 ms 3184 KB Output is correct
24 Correct 4 ms 3184 KB Output is correct
25 Correct 5 ms 3184 KB Output is correct
26 Correct 4 ms 3184 KB Output is correct
27 Correct 5 ms 3184 KB Output is correct
28 Correct 4 ms 3184 KB Output is correct
29 Correct 4 ms 3184 KB Output is correct
30 Correct 4 ms 3184 KB Output is correct
31 Correct 4 ms 3184 KB Output is correct
32 Correct 4 ms 3184 KB Output is correct
33 Correct 4 ms 3184 KB Output is correct
34 Correct 4 ms 3184 KB Output is correct
35 Correct 4 ms 3184 KB Output is correct
36 Correct 4 ms 3184 KB Output is correct
37 Correct 4 ms 3184 KB Output is correct
38 Correct 27 ms 3188 KB Output is correct
39 Execution timed out 1073 ms 3192 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2920 KB Output is correct
4 Correct 4 ms 2920 KB Output is correct
5 Correct 4 ms 3036 KB Output is correct
6 Correct 4 ms 3044 KB Output is correct
7 Correct 5 ms 3044 KB Output is correct
8 Correct 5 ms 3160 KB Output is correct
9 Correct 19 ms 3160 KB Output is correct
10 Correct 325 ms 3184 KB Output is correct
11 Correct 5 ms 3184 KB Output is correct
12 Correct 5 ms 3184 KB Output is correct
13 Correct 4 ms 3184 KB Output is correct
14 Correct 4 ms 3184 KB Output is correct
15 Correct 5 ms 3184 KB Output is correct
16 Correct 4 ms 3184 KB Output is correct
17 Correct 5 ms 3184 KB Output is correct
18 Correct 5 ms 3184 KB Output is correct
19 Correct 4 ms 3184 KB Output is correct
20 Correct 4 ms 3184 KB Output is correct
21 Correct 5 ms 3184 KB Output is correct
22 Correct 4 ms 3184 KB Output is correct
23 Correct 5 ms 3184 KB Output is correct
24 Correct 4 ms 3184 KB Output is correct
25 Correct 5 ms 3184 KB Output is correct
26 Correct 4 ms 3184 KB Output is correct
27 Correct 5 ms 3184 KB Output is correct
28 Correct 4 ms 3184 KB Output is correct
29 Correct 4 ms 3184 KB Output is correct
30 Correct 4 ms 3184 KB Output is correct
31 Correct 4 ms 3184 KB Output is correct
32 Correct 4 ms 3184 KB Output is correct
33 Correct 4 ms 3184 KB Output is correct
34 Correct 4 ms 3184 KB Output is correct
35 Correct 4 ms 3184 KB Output is correct
36 Correct 4 ms 3184 KB Output is correct
37 Correct 4 ms 3184 KB Output is correct
38 Correct 27 ms 3188 KB Output is correct
39 Execution timed out 1073 ms 3192 KB Time limit exceeded
40 Halted 0 ms 0 KB -