oj.uz

Submission #978762

# Submission time Handle Problem Language Result Execution time Memory
978762 2024-05-09T15:31:27 Z De3b0o Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x%y);
}

string tb(ll x)
{
    string s = "";
    while(x>0)
    {
        if(x&1)
            s+='1';
        else
            s+='0';
        x/=2;
    }
    while(s.size()<60)
        s+='0';
    return s;
}

ll fb(string s)
{
    ll x = 0;
    ll c = 1;
    for(int8_t i = 0 ; 60>i ; i++)
    {
        if(s[i]=='1')
            x+=c;
        c*=2;
    }
    return x;
}

ll n , m;
vector<ll> adj[100009];
vector<ll> v;
bool vis[100009];
ll sz;
ll st[100009];
ll ans;

void dfs(ll n , ll p)
{
    vis[n]=1;
    sz++;
    st[n]=1;
    for(auto it : adj[n])
    {
        if(it==p)
            continue;
        dfs(it,n);
        st[n]+=st[it];
    }
}

void dpt(ll n , ll p)
{
    ans+=(sz-st[n])*(st[n]-1);
    for(auto it : adj[n])
    {
        if(it==p)
            continue;
        ans+=(sz-1-st[it])*(st[it]);
        dpt(it,n);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0 ; m>i ; i++)
    {
        ll u , v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1 ; n>=i ; i++)
    {
        if(vis[i])
            continue;
        sz=0;
        dfs(i,0);
        dpt(i,0);
    }
    cans
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8524 KB Output is correct
2 Correct 57 ms 8528 KB Output is correct
3 Correct 56 ms 8508 KB Output is correct
4 Correct 57 ms 8452 KB Output is correct
5 Correct 57 ms 8532 KB Output is correct
6 Correct 72 ms 11248 KB Output is correct
7 Correct 61 ms 10600 KB Output is correct
8 Correct 63 ms 10124 KB Output is correct
9 Correct 61 ms 9508 KB Output is correct
10 Correct 62 ms 8464 KB Output is correct
11 Correct 58 ms 8444 KB Output is correct
12 Correct 57 ms 8600 KB Output is correct
13 Correct 70 ms 8400 KB Output is correct
14 Correct 53 ms 8284 KB Output is correct
15 Correct 45 ms 7760 KB Output is correct
16 Correct 34 ms 6572 KB Output is correct
17 Correct 55 ms 8648 KB Output is correct
18 Correct 51 ms 8772 KB Output is correct
19 Correct 56 ms 8828 KB Output is correct
20 Correct 49 ms 8772 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Runtime error 703 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8628 KB Output is correct
2 Correct 57 ms 8436 KB Output is correct
3 Runtime error 754 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -