Submission #13176

#	Time	Username	Problem	Language	Result	Execution time	Memory
13176		woqja125	Shymbulak (IZhO14_shymbulak)	C++98	Compilation error	0 ms	0 KiB

shymbulak

#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;
}

Compilation message (stderr)

shymbulak.cpp: In function ‘int main()’:
shymbulak.cpp:34:20: error: range-based ‘for’ loops are not allowed in C++98 mode
         for(int t :map[x]) if(v[t] == false){ xx=t; break; }
                    ^
shymbulak.cpp:51:20: error: range-based ‘for’ loops are not allowed in C++98 mode
         for(int t: map[xx]) if(!v[t]){ tx = t; break;}
                    ^
shymbulak.cpp:14:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
shymbulak.cpp:17:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &xx);
                               ^