Submission #647168

#	Time	Username	Problem	Language	Result	Execution time	Memory
647168		MohamedAliSaidane	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5056 ms	9528 KiB

diameter

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define pb push_back
#define all(x) (x).begin(),(x).end()

#define ff first
#define ss second

const int nax = 1e5 + 4;
int n, q;
ll W;
vector<pii> adj[nax];
ll weig[nax];
void solve()
{
    cin >> n >> q >> W;
    for(int i = 1 ; i < n ;i ++)
    {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        weig[i] = w;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    ll last = 0ll;
    while(q --)
    {
        ll d, e;
        cin >> d >> e;
        d = (d + last)%(n - 1);
        e = (e + last)%W;
        d++;
        weig[d] = e;
        queue<pll> q;
        q.push({1, 0});
        pll maxi = {0, 1};\
        bool vis[n + 1];
        memset(vis, 0, sizeof(vis));
        while(!q.empty())
        {
            int node = q.front().ff;
            vis[node] = 1;
            ll dis = q.front().ss;
            q.pop();
            maxi = max(maxi, {dis, node});
            for(auto u: adj[node])
            {
                int nei = u.ff;
                int idx = u.ss;
                if(vis[nei])
                    continue;
                q.push({nei, dis+ weig[idx]});
            }
        }
        memset(vis, false, sizeof(vis));
        q.push({maxi.ss, 0});
        //cout << maxi.ss << ' ';
        while(!q.empty())
        {
            int node = q.front().ff;
            ll dis = q.front().ss;
            q.pop();
            vis[node] = 1;
            maxi= max(maxi, {dis, node});
            for(auto u: adj[node])
            {
                int nei = u.ff;
                int idx = u.ss;
                if(vis[nei])
                    continue;
                q.push({nei, dis + weig[idx]});
            }
        }
        cout << maxi.ff << '\n';
        last = maxi.ff;
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt -- )
        solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27