Submission #469061

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469061	2021-08-30T14:44:11 Z	Carmel_Ab1	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	694 ms	44132 KB

diameter

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}

void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}

template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}

template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t:a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}

ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}

ld log(ld a, ld b) { return log(b) / log(a); }

ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}

string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}

vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}

string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}


void solve();

int main() {
    GLHF;
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}
vvi g;
umap<ll,umap<ll,ll>>c;
vl dijkstra(ll src){
    ll n=g.size()-1;
    vl d(n+1,1e18);
    priority_queue<vl,vvl,greater<vl>>pq;//{dst,node}
    pq.push({0,src});
    vector<bool>vis(n+1);

    while(pq.size()){
        vl v=pq.top();
        pq.pop();
        src=v[1];
        ll dst=v[0];
        if(vis[src])continue;
        vis[src]=1;
        d[src]=dst;
        for(int nbr:g[src])
            if(!vis[nbr])
                pq.push({dst+c[src][nbr],nbr});
    }
    return d;
}
multiset<ll>s;
ll calc(){
    ll mx=*s.rbegin();
    if(s.size()==1)
        return mx;
    s.erase(s.find(mx));
    ll mx2=*s.rbegin();
    s.insert(mx);
    return mx+mx2;
}
void solve() {
    ll n,q,maxw;
    cin >> n >> q >> maxw;
    g.resize(n+1);

    vpl E(n-1);
    for(int i=0; i<n-1; i++){
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb(v);
        g[v].pb(u);
        c[u][v]=c[v][u]=w;
        E[i]={u,v};
        s.insert(w);
    }
    ll ans=0;
    while(q--){
        ll d,w;
        cin >> d >> w;
        d=(ans+d)%(n-1);
        w=(ans+w)%maxw;
        ll v=E[d].first,u=E[d].second;
        s.erase(s.find(c[u][v]));
        c[u][v]=c[v][u]=w;
        s.insert(w);
        ans=calc();
        cout << ans<< "\n";
    }
}

Compilation message

diameter.cpp: In function 'void usaco(std::string)':
diameter.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 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	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	2 ms	204 KB	Output is correct
4	Correct	12 ms	328 KB	Output is correct
5	Correct	50 ms	616 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	14 ms	616 KB	Output is correct
11	Correct	67 ms	960 KB	Output is correct
12	Correct	7 ms	2252 KB	Output is correct
13	Correct	8 ms	2252 KB	Output is correct
14	Correct	8 ms	2252 KB	Output is correct
15	Correct	27 ms	2272 KB	Output is correct
16	Correct	84 ms	2692 KB	Output is correct
17	Correct	217 ms	41340 KB	Output is correct
18	Correct	208 ms	41300 KB	Output is correct
19	Correct	198 ms	41444 KB	Output is correct
20	Correct	239 ms	41616 KB	Output is correct
21	Correct	584 ms	43000 KB	Output is correct