oj.uz

Submission #13177

# Submission time Handle Problem Language Result Execution time Memory
13177 2015-02-01T12:15:15 Z woqja125 Shymbulak (IZhO14_shymbulak) C++14
55 / 100
 128 ms 30504 KB 
#include<stdio.h>
#include<vector>
#include<queue>
std::vector<int> map[200001];
int deg[200001];
int n;
int dist[200001], distC[200001];
int v[200001];
int cycles[200001], CC = 0;
long long solve();
int main()
{
    int i, x, xx;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &x, &xx);
        map[x].push_back(xx);
        map[xx].push_back(x);
        deg[x]++;
        deg[xx]++;
    }
    std::queue<int> Q;
    for(i=1; i<=n; i++)
    {
        if(deg[i] == 1)Q.push(i);
        distC[i] = 1;
    }
    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        v[x] = true;
        for(int t :map[x]) if(v[t] == false){ xx=t; break; }
        deg[xx]--;
        if(deg[xx] == 1) Q.push(xx);
        if(dist[xx] < dist[x]+1)
        {
            dist[xx] = dist[x]+1;
            distC[xx] = distC[x];
        }
        else if(dist[xx] == dist[x] + 1) distC[xx]+=distC[x];
    }
    for(i=1; i<=n; i++) if(deg[i] != 1) break;
    xx = x = i;
    do
    {
        v[xx] = true;
        cycles[CC++] = xx;
        int tx=-1;
        for(int t: map[xx]) if(!v[t]){ tx = t; break;}
        xx = tx;
    }while(xx!=-1);
    printf("%lld", solve());
    return 0;
}
 
int im[1050000];
long long imc[1050000];
int b;
 
inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}
 
void add(int &m, long long &mC, int m1, long long mc1, int m2, long long mc2)
{
    if(m1 == m2)
    {
        m = m1;
        mC = mc1 + mc2;
    }
    else if(m1 > m2)
    {
        m = m1;
        mC = mc1;
    }
    else
    {
        m = m2;
        mC = mc2;
    }
}
 
void get(int &rm, long long &rmc, int f, int r)
{
    f+=b; r+=b;
    rm = rmc = 0;
    while(f<r)
    {
        if(f%2 == 1) { add(rm, rmc, rm, rmc, im[f], imc[f]); f++; }
        if(r%2 == 0) { add(rm, rmc, rm, rmc, im[r], imc[r]); r--; }
        f/=2; r/=2;
    }
    if(f==r) add(rm, rmc, rm, rmc, im[f], imc[f]);
}
 
long long solve()
{
    int i;
    for(b=1; b<=2*CC; b*=2);
    for(i=0; i<2*CC; i++)
    {
        im[b+i] = cn(i) + i;
        imc[b+i] = cd(i);
    }
    for(i=b-1; i>=1; i--) add(im[i], imc[i], im[i*2], imc[i*2], im[i*2+1], imc[i*2+1]);
    int max = 0, tm;
    long long maxC = 0, tmc;
    int j;
    for(j=0; j-i <= CC-j; j++);
    for(i=0; i<CC; i++)
    {
        get(tm, tmc, i+1, j-1);
        add(max, maxC, max, maxC, tm-i+cn(i), tmc*cd(i));
        j++;
    }
    return maxC;
}

Subtask #1
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22480 KB Output is correct
2 Incorrect 0 ms 22480 KB Output isn't correct
3 Correct 0 ms 22480 KB Output is correct
4 Correct 0 ms 22480 KB Output is correct
5 Incorrect 3 ms 22480 KB Output isn't correct
6 Incorrect 0 ms 22480 KB Output isn't correct
7 Correct 0 ms 22480 KB Output is correct
8 Correct 0 ms 22480 KB Output is correct
9 Incorrect 0 ms 22480 KB Output isn't correct
10 Incorrect 0 ms 22480 KB Output isn't correct
11 Correct 3 ms 22480 KB Output is correct
12 Correct 3 ms 22480 KB Output is correct
13 Incorrect 0 ms 22480 KB Output isn't correct
14 Correct 2 ms 22480 KB Output is correct
15 Correct 0 ms 22480 KB Output is correct

Subtask #2
12.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 22480 KB Output is correct
2 Incorrect 0 ms 22480 KB Output isn't correct
3 Correct 2 ms 22480 KB Output is correct
4 Correct 0 ms 22480 KB Output is correct
5 Correct 5 ms 22612 KB Output is correct
6 Incorrect 3 ms 22612 KB Output isn't correct
7 Incorrect 4 ms 22612 KB Output isn't correct
8 Incorrect 4 ms 22612 KB Output isn't correct
9 Correct 0 ms 22612 KB Output is correct
10 Correct 3 ms 22612 KB Output is correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 25644 KB Output isn't correct
2 Incorrect 55 ms 26044 KB Output isn't correct
3 Correct 24 ms 25648 KB Output is correct
4 Correct 53 ms 25776 KB Output is correct
5 Correct 21 ms 25908 KB Output is correct
6 Incorrect 128 ms 28416 KB Output isn't correct
7 Incorrect 63 ms 27492 KB Output isn't correct
8 Correct 83 ms 29208 KB Output is correct
9 Correct 103 ms 29208 KB Output is correct
10 Correct 75 ms 29608 KB Output is correct
11 Incorrect 124 ms 30108 KB Output isn't correct
12 Incorrect 104 ms 30504 KB Output isn't correct