oj.uz

답안 #304545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304545 2020-09-21T13:27:00 Z vipghn2003 꿈 (IOI13_dreaming) C++14
0 / 100
 58 ms 18040 KB 
#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,cnt,l[N],r[N],Time,root,dep[N],last,ST[4*N],lazy[4*N];
pii val[N];
vector<int>adj[N],a,b,w;
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 a[],int b[],int w[])
{
    n=num;
    for(int i=0;i<m;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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 14720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 58 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -