답안 #469058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469058	2021-08-30T14:42:02 Z	Carmel_Ab1	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	449 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;
        assert(s.size()==n-1);
        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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from diameter.cpp:1:
diameter.cpp: In function 'void solve()':
diameter.cpp:195:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  195 |         assert(s.size()==n-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
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	9 ms	452 KB	Output is correct
5	Correct	48 ms	1436 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	2 ms	2380 KB	Output is correct
8	Correct	2 ms	2380 KB	Output is correct
9	Correct	3 ms	2380 KB	Output is correct
10	Correct	13 ms	2628 KB	Output is correct
11	Correct	58 ms	3636 KB	Output is correct
12	Correct	109 ms	196980 KB	Output is correct
13	Correct	106 ms	196932 KB	Output is correct
14	Correct	107 ms	196944 KB	Output is correct
15	Correct	121 ms	197212 KB	Output is correct
16	Correct	176 ms	198468 KB	Output is correct
17	Runtime error	449 ms	1048580 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-