Submission #618638

#	Time	Username	Problem	Language	Result	Execution time	Memory
618638		Je_O	Dynamic Diameter (CEOI19_diameter)	C++17	11 / 100	5096 ms	3400 KiB

diameter

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 5e3 + 5;
const int INF = 1e9;
vector<iii> vec;
vector<ii> lst[N];
int dist[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q, w; cin >> n >> q >> w;
    for(int i = 0; i < n - 1; ++i){
        int a, b, c; cin >> a >> b >> c;
        vec.pb(mp(c, mp(a, b)));
    }
    int last = 0;
    while(q--){
        int d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        vec[d].fi = e;
        for(int i = 1; i <= n; ++i)lst[i].clear();
        for(int i = 0; i < n - 1; ++i){
            lst[vec[i].se.fi].pb(mp(vec[i].se.se, vec[i].fi));
            lst[vec[i].se.se].pb(mp(vec[i].se.fi, vec[i].fi));
        }
        for(int i = 1; i <= n; ++i)dist[i] = INF;
        priority_queue<ii, vector<ii>, greater<ii> > pq;
        pq.push(mp(0, 1));
        dist[1] = 0;
        while(!pq.empty()){
            ii cur = pq.top(); pq.pop();
            for(int i = 0; i < lst[cur.se].size(); ++i){
                int nx = lst[cur.se][i].fi;
                int cs = cur.fi + lst[cur.se][i].se;
                if(cs < dist[nx]){
                    dist[nx] = cs;
                    pq.push(mp(cs, nx));
                }
            }
        }
        ii maxdist = mp(-1, -1);
        for(int i = 1; i <= n; ++i){
            maxdist = max(maxdist, mp(dist[i], i));
        }
        for(int i = 1; i <= n; ++i)dist[i] = INF;
        pq.push(mp(0, maxdist.se));
        dist[maxdist.se] = 0;
        while(!pq.empty()){
            ii cur = pq.top(); pq.pop();
            for(int i = 0; i < lst[cur.se].size(); ++i){
                int nx = lst[cur.se][i].fi;
                int cs = cur.fi + lst[cur.se][i].se;
                if(cs < dist[nx]){
                    dist[nx] = cs;
                    pq.push(mp(cs, nx));
                }
            }
        }
        int ans = -1;
        for(int i = 1; i <= n; ++i){
            ans = max(ans, dist[i]);
        }
        last = ans;
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:41:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int i = 0; i < lst[cur.se].size(); ++i){
      |                            ~~^~~~~~~~~~~~~~~~~~~~
diameter.cpp:59:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(int i = 0; i < lst[cur.se].size(); ++i){
      |                            ~~^~~~~~~~~~~~~~~~~~~~

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