Submission #909134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
909134	2024-01-17T05:43:38 Z	ibm2006	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	420 ms	48720 KB

diameter

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,h[1100000],ans,qu;
vector<pair<ll,ll>> v[1100000];
pair<ll,ll> pq;
multiset<ll> st;
pair<ll,pair<ll,ll>> p[1100000],q[1100000];
pair<ll,ll> f(ll x,ll y)
{
    ll i;
    pair<ll,ll> p={x,0},q;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i].first==y)
            continue;
        q=f(v[x][i].first,x);
        if(q.second+v[x][i].second>p.second)
        {
            p={q.first,q.second+v[x][i].second};
        }
    }
    return p;
}
int main()
{
    scanf("%lld %lld %lld",&n,&qu,&w);
    for(i=1;i<n;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        st.insert(-z);
        p[i]={x,{h[x],z}};
        q[i]={y,{h[y],z}};
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        h[x]++;
        h[y]++;
    }
    for(i=1;i<=qu;i++)
    {
        scanf("%lld %lld",&x,&y);
        x=(x+ans)%(n-1);
        y=(y+ans)%w;
        x++;
        v[p[x].first][p[x].second.first].second=y;
        st.erase(st.find(-p[x].second.second));
        p[x].second.second=y;
        st.insert(-y);
         v[q[x].first][q[x].second.first].second=y;
        q[x].second.second=y;
        //pq=f(1,0);
        //ans=f(pq.first,0).second;
        if(n==2)
            ans=(*st.begin());
            else
            ans=(*st.begin())+(*(++st.begin()));
            ans*=-1;
        printf("%lld\n",ans);
    }
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%lld %lld %lld",&n,&qu,&w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld %lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	29176 KB	Output is correct
2	Correct	9 ms	29020 KB	Output is correct
3	Correct	9 ms	29020 KB	Output is correct
4	Correct	15 ms	29016 KB	Output is correct
5	Correct	41 ms	29524 KB	Output is correct
6	Correct	8 ms	29020 KB	Output is correct
7	Correct	8 ms	29172 KB	Output is correct
8	Correct	8 ms	29020 KB	Output is correct
9	Correct	9 ms	29016 KB	Output is correct
10	Correct	17 ms	29276 KB	Output is correct
11	Correct	45 ms	29536 KB	Output is correct
12	Correct	10 ms	29528 KB	Output is correct
13	Correct	10 ms	29532 KB	Output is correct
14	Correct	13 ms	29704 KB	Output is correct
15	Correct	19 ms	29788 KB	Output is correct
16	Correct	56 ms	30032 KB	Output is correct
17	Correct	88 ms	44800 KB	Output is correct
18	Correct	68 ms	44996 KB	Output is correct
19	Correct	69 ms	44888 KB	Output is correct
20	Correct	113 ms	45264 KB	Output is correct
21	Correct	232 ms	48076 KB	Output is correct