Submission #1244401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244401		riddles	Dreaming (IOI13_dreaming)	C++20	0 / 100	1096 ms	16704 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef map<ll, ll> mp;
typedef pair<ll, ll> pll;
typedef queue<ll> qi;
typedef vector<ll> vi;
typedef vector <vi> vvi;
typedef vector <pll> vpl;
typedef vector <string> vs;
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define F first
#define S second
#define pb push_back
#define all(x) begin(x), end(x)
#define MAXN 100001

ll br=0, t=1, sl=-1;
vector<pll> adj[MAXN];
ll comp[MAXN],dist[MAXN];
ll tin[MAXN], to[MAXN],fenw[MAXN+1];
vi nds[MAXN];
vi answ;

void dfs(ll nd, ll pr){
    comp[nd]=br;
    nds[br].pb(nd);
    for (pll par: adj[nd]){
        ll s=par.F, w=par.S;
        if(s==pr) continue;
        dist[s]=dist[nd]+w;
        dfs(sl, nd);
    }
}

void dfs1(ll nd, ll pr) {
    tin[nd]=t;
    t++;
    for (pll par: adj[nd]) {
        ll s=par.F, w=par.S;
        if (s == pr) continue;
        dist[s] = dist[nd] + w;
        dfs1(s, nd);
    }
    to[nd]=t-1;
}

void update(ll pos, ll val) {
    for (ll i=pos; i <=t + 1; i+=i&(-i)) fenw[i] += val;
}

ll query(ll pos) {
    ll sum=0;
    for (ll i=pos; i>0; i-=i&(-i)) sum+=fenw[i];
    return sum;
}

void resi(ll comp, ll n) {
    ll maxdist=0, maxnode=nds[comp][0];
    for (ll node: nds[comp]) {
        if (dist[node] > maxdist) {
            maxdist=dist[node];
            maxnode=node;
        }
    }
    t=1; dist[maxnode]=0; dfs1(maxnode, 0);
    ll len=0, sol=len;
    for (ll i=1; i<=t+1; i++) fenw[i]=0;
    for (ll node: nds[comp]) {
        len=max(len, dist[node]);
        sol=len;
    }
    for (ll node: nds[comp]) {
        if (dist[node] == len) update(tin[node], 1);
    }
    for (ll node: nds[comp]) {
        ll value=max(dist[node], len-dist[node]);
        if (value >= sol) continue;
        if (value == dist[node]) {
            sol=min(sol, value);
            continue;
        }
        ll broj=query(to[node]) - query(tin[node]-1);
        if (broj > 0) sol=min(sol, value);
    }
    answ.pb(sol);
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for (int i=0; i<m; i++) {
        int node1=a[i]+1, node2=b[i]+1, wp=t[i];
        adj[node1].pb({node2, wp});
        adj[node2].pb({node1, wp});
    }
    for(int node=1; node<=n; node++) {
        if (comp[node] == 0) {
            br++;
            dfs(node, 0);
        }
    }
    for (int i=1; i<=br; i++) resi(i, n);
    sort(answ.begin(), answ.end());
    int ans=0;
    for (int i=0; i<answ.size(); i++) {
        if (answ[i] > sl) {
            ans++;
            sl = answ[i];
        }
    }
    sort(all(answ));
    
    if (answ.size() != 1) ans = max(ans, answ[answ.size()-1] + answ[answ.size()-2] + l);
    return ans;
}

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