oj.uz

Submission #469121

# Submission time Handle Problem Language Result Execution time Memory
469121 2021-08-30T20:21:06 Z Carmel_Ab1 Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 5000 ms 43036 KB 
#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 par,dep,mx,diam;
multiset<ll>s;
void dfs(int src,int p){
    par[src]=p;
    if(p!=-1)
        dep[src]=dep[p]+1;
    ll mx1=-1,mx2=-1;
    vl v;
    for(int nbr:g[src])
        if(nbr!=par[src]){
            dfs(nbr,src);
            mx[src]=max(mx[src],mx[nbr]+c[src][nbr]);
            v.pb(mx[nbr]+c[src][nbr]);
        }
    sort(all(v));
    if(v.size()>1){
        mx1=v[v.size()-1],mx2=v[v.size()-2];
        diam[src]=mx1+mx2;
        s.insert(diam[src]);
    }
}

void calc(ll src){
    int n=g.size()-1;
    while(src!=-1){
        mx[src]=0;
        for(int nbr:g[src])
            if(nbr!=par[src])
                mx[src]=max(mx[src],mx[nbr]+c[src][nbr]);
        ll mx1=-1,mx2=-1;
        if(s.count(diam[src]))
            s.erase(s.find(diam[src]));
        vl v;
        for(int nbr:g[src])
            if(nbr!=par[src]){
                v.pb(mx[nbr]+c[src][nbr]);
            }
        sort(all(v));
        if(v.size()>1){
            mx1=v[v.size()-1],mx2=v[v.size()-2];
            diam[src]=mx1+mx2;
            s.insert(diam[src]);
        }
        src=par[src];
    }


}
void solve() {
    ll n,q,maxw;
    cin >> n >> q >> maxw;
    g.resize(n+1);

    vpl E(n-1);
    vi deg(n+1);
    int rt=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};
        deg[u]++,deg[v]++;
        if(deg[u]>1)
            rt=u;
        if(deg[v]>1)
            rt=v;
    }

    dep.resize(n+1);
    par.resize(n+1,-1);
    mx.resize(n+1);
    diam.resize(n+1);
    if(n!=2)
        dfs(rt,-1);

    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;
        c[u][v]=c[v][u]=w;
        if(n==2){
            cout << w << "\n";
            continue;
        }
        calc((dep[u]<dep[v])?u:v);
        cout << (ans=*s.rbegin()) << "\n";

    }
}

Compilation message

diameter.cpp: In function 'void calc(ll)':
diameter.cpp:167:9: warning: unused variable 'n' [-Wunused-variable]
  167 |     int n=g.size()-1;
      |         ^
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
11.0 / 11.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 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 312 KB Output is correct

Subtask #2
13.0 / 13.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 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 38 ms 764 KB Output is correct
20 Correct 55 ms 836 KB Output is correct
21 Correct 158 ms 772 KB Output is correct
22 Correct 165 ms 860 KB Output is correct
23 Correct 49 ms 2252 KB Output is correct
24 Correct 149 ms 2252 KB Output is correct
25 Correct 512 ms 2524 KB Output is correct
26 Correct 1263 ms 3260 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 31 ms 388 KB Output is correct
5 Correct 154 ms 712 KB Output is correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 700 KB Output is correct
2 Correct 55 ms 820 KB Output is correct
3 Correct 211 ms 1380 KB Output is correct
4 Correct 424 ms 2084 KB Output is correct
5 Correct 20 ms 4300 KB Output is correct
6 Correct 85 ms 4436 KB Output is correct
7 Correct 359 ms 5276 KB Output is correct
8 Correct 706 ms 5912 KB Output is correct
9 Correct 83 ms 20692 KB Output is correct
10 Correct 177 ms 20900 KB Output is correct
11 Correct 561 ms 21568 KB Output is correct
12 Correct 1055 ms 22540 KB Output is correct
13 Correct 166 ms 41144 KB Output is correct
14 Correct 259 ms 41344 KB Output is correct
15 Correct 718 ms 42040 KB Output is correct
16 Correct 1270 ms 43036 KB Output is correct
17 Correct 2049 ms 42572 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 39048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 38 ms 764 KB Output is correct
20 Correct 55 ms 836 KB Output is correct
21 Correct 158 ms 772 KB Output is correct
22 Correct 165 ms 860 KB Output is correct
23 Correct 49 ms 2252 KB Output is correct
24 Correct 149 ms 2252 KB Output is correct
25 Correct 512 ms 2524 KB Output is correct
26 Correct 1263 ms 3260 KB Output is correct
27 Correct 0 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 4 ms 332 KB Output is correct
30 Correct 31 ms 388 KB Output is correct
31 Correct 154 ms 712 KB Output is correct
32 Incorrect 0 ms 204 KB Output isn't correct
33 Halted 0 ms 0 KB -