oj.uz

Submission #75371

# Submission time Handle Problem Language Result Execution time Memory
75371 2018-09-09T13:15:06 Z born2rule Duathlon (APIO18_duathlon) C++14
31 / 100
 139 ms 28000 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<void (int, vi&)> dfs = [&](int u,vi &tmp)->void
    {
      vis[u]=true; tmp.pb(u);
      for(int v1:v[u]) if(!vis[v1]) dfs(v1,tmp);
    };
  memset(vis,false,sizeof(vis));
  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));
    }
  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]-(ll)child[v1]-1)*(ll)(d[u]*2+1);
	}
      ans+=(ll)(sumd[u]-(ll)(child[u]-1)*(ll)(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(checksub45()) return 0;// a tree
  if(checksub3()) return 0; //degree at most 2
  if(checksub12()) return 0;//brute
  return 0 ;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 17012 KB Output is correct
2 Correct 102 ms 17012 KB Output is correct
3 Correct 82 ms 17012 KB Output is correct
4 Correct 108 ms 17012 KB Output is correct
5 Correct 86 ms 17012 KB Output is correct
6 Correct 73 ms 17012 KB Output is correct
7 Correct 81 ms 17012 KB Output is correct
8 Correct 77 ms 17012 KB Output is correct
9 Correct 72 ms 17012 KB Output is correct
10 Correct 64 ms 17284 KB Output is correct
11 Correct 63 ms 17284 KB Output is correct
12 Correct 67 ms 17284 KB Output is correct
13 Correct 55 ms 17916 KB Output is correct
14 Correct 55 ms 18828 KB Output is correct
15 Correct 63 ms 19320 KB Output is correct
16 Correct 43 ms 19860 KB Output is correct
17 Correct 7 ms 19860 KB Output is correct
18 Correct 7 ms 19860 KB Output is correct
19 Correct 7 ms 19860 KB Output is correct
20 Correct 8 ms 19860 KB Output is correct
21 Correct 7 ms 19860 KB Output is correct
22 Correct 7 ms 19860 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 22152 KB Output is correct
2 Correct 75 ms 22184 KB Output is correct
3 Correct 66 ms 22208 KB Output is correct
4 Correct 80 ms 22208 KB Output is correct
5 Correct 108 ms 22280 KB Output is correct
6 Correct 139 ms 28000 KB Output is correct
7 Correct 96 ms 28000 KB Output is correct
8 Correct 106 ms 28000 KB Output is correct
9 Correct 101 ms 28000 KB Output is correct
10 Correct 69 ms 28000 KB Output is correct
11 Correct 85 ms 28000 KB Output is correct
12 Correct 75 ms 28000 KB Output is correct
13 Correct 79 ms 28000 KB Output is correct
14 Correct 81 ms 28000 KB Output is correct
15 Correct 63 ms 28000 KB Output is correct
16 Correct 40 ms 28000 KB Output is correct
17 Correct 60 ms 28000 KB Output is correct
18 Correct 53 ms 28000 KB Output is correct
19 Correct 59 ms 28000 KB Output is correct
20 Correct 57 ms 28000 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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