Submission #469056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469056	2021-08-30T14:39:04 Z	Carmel_Ab1	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	568 ms	1048580 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;
vector<vl>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);
    c.resize(n+1,vl(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(c[u][v]);
        ans=calc();
        cout << ans<< "\n";
    }
}

Compilation message

diameter.cpp: In function 'std::vector<_Tp> UNQ(std::vector<_Tp>)':
diameter.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |     for (T t:a)
      |     ^~~
diameter.cpp:73:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |         return ans;
      |         ^~~~~~
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
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	332 KB	Output is correct
4	Correct	10 ms	536 KB	Output is correct
5	Correct	45 ms	1440 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	2 ms	2364 KB	Output is correct
8	Correct	2 ms	2252 KB	Output is correct
9	Correct	3 ms	2368 KB	Output is correct
10	Correct	13 ms	2648 KB	Output is correct
11	Correct	58 ms	3596 KB	Output is correct
12	Correct	87 ms	196932 KB	Output is correct
13	Correct	87 ms	197004 KB	Output is correct
14	Correct	91 ms	196924 KB	Output is correct
15	Correct	104 ms	197188 KB	Output is correct
16	Correct	160 ms	198360 KB	Output is correct
17	Runtime error	568 ms	1048580 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-