Submission #304548

#	Time	Username	Problem	Language	Result	Execution time	Memory
304548		vipghn2003	Dreaming (IOI13_dreaming)	C++14	100 / 100	399 ms	23776 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=1e5+5;
int n,m,a[N],b[N],w[N],cnt,l[N],r[N],Time,root,dep[N],last,ST[4*N],lazy[4*N];
pii val[N];
vector<int>adj[N];
vector<pii>g[N];
bool vis[N];
vector<int>go;

void dolazy(int id,int l,int r)
{
    if (lazy[id]==0) return;
    ST[id]+=lazy[id];
    if (l!=r)
    {
        lazy[id*2]+=lazy[id];
        lazy[id*2+1]+=lazy[id];
    }
    lazy[id]=0;
}

void update(int id,int l,int r,int L,int R,int val)
{
    dolazy(id,l,r);
    if (r<L||R<l) return;
    if(L<=l&&r<=R)
    {
        ST[id]+=val;
        if (l!=r)
        {
            lazy[id*2]+=val;
            lazy[id*2+1]+=val;
        }
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,L,R,val);
    update(id*2+1,mid+1,r,L,R,val);
    ST[id]=max(ST[id*2],ST[id*2+1]);
}

int get (int id,int l,int r,int L,int R)
{
    dolazy(id,l,r);
    if (r<L||R<l) return -1e9;
    if (L<=l&&r<=R) return ST[id];
    int mid=(l+r)/2;
    return max (get (id*2,l,mid,L,R),get (id*2+1,mid+1,r,L,R));
}

void dfs(int u)
{
    go.push_back(u);
    vis[u]=true;
    Time++;
    l[u]=Time;
    for(auto&id:adj[u])
    {
        int v=a[id]+b[id]-u;
        if(vis[v]) continue;
        dep[v]=dep[u]+w[id];
        dfs(v);
    }
    r[u]=Time;
}

void calc(int u)
{
    vis[u]=true;
    val[cnt]=min(val[cnt],mp(get(1,1,n,l[root],r[root]),u));
    //if(root==0) cout<<u<<' '<<l[root]<<' '<<r[root]<<' '<<get(1,1,n,l[root],r[root])<<' '<<val[cnt].fi<<'\n';
    for(auto&id:adj[u])
    {
        int v=a[id]+b[id]-u;
        if(vis[v]) continue;
        update(1,1,n,l[root],r[root],w[id]);
        update(1,1,n,l[v],r[v],-2*w[id]);
        calc(v);
        update(1,1,n,l[root],r[root],-w[id]);
        update(1,1,n,l[v],r[v],2*w[id]);
    }
}

void fin(int u,int p)
{
    if(dep[u]>dep[last]) last=u;
    for(auto&v:g[u])
    {
        if(v.fi==p) continue;
        dep[v.fi]=dep[u]+v.se;
        fin(v.fi,u);
    }
}

int travelTime(int num,int m,int t,int aa[],int bb[],int ww[])
{
    n=num;
    for(int i=0;i<m;i++)
    {
        a[i]=aa[i];
        b[i]=bb[i];
        w[i]=ww[i];
        adj[a[i]].push_back(i);
        adj[b[i]].push_back(i);
    }
    cnt=0;
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            root=i;
            go.clear();
            dfs(i);
            for(auto&u:go)
            {
                //if(!i) cout<<l[u]<<' '<<dep[u]<<'\n';
                vis[u]=false;
                update(1,1,n,l[u],l[u],dep[u]);
            }
            //cout<<'\n';
            cnt++;
            val[cnt]=mp(1e9,0);
            calc(i);
            //cout<<val[cnt].fi<<'\n';
        }
    }
    sort(val+1,val+cnt+1);
    int p=val[cnt].se;
    for(int i=cnt-1;i>=1;i--)
    {
        g[p].push_back(mp(val[i].se,t));
        g[val[i].se].push_back(mp(p,t));
        //cout<<val[i].se<<' '<<p<<' '<<t<<'\n';
    }
    for(int i=0;i<m;i++)
    {
        g[a[i]].push_back(mp(b[i],w[i]));
        g[b[i]].push_back(mp(a[i],w[i]));
        //cout<<a[i]<<' '<<b[i]<<' '<<w[i]<<'\n';
    }
    fin(0,-1);
    dep[last]=0;
    fin(last,-1);
    return dep[last];
}

/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int l;
    cin>>n>>m>>l;
    a.resize(m),b.resize(m),w.resize(m);
    for(int i=0;i<m;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<m;i++) cin>>w[i];
    cout<<travelTime(n,m,l,a,b,w);
}
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23