Submission #858717

#	Time	Username	Problem	Language	Result	Execution time	Memory
858717		damwuan	Dreaming (IOI13_dreaming)	C++17	100 / 100	55 ms	22724 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const ll maxn=2e5+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;

vector<int> adj[maxn];
bool vis[maxn];
int a[maxn],b[maxn],t[maxn],dep[maxn],g;
int dfs(int u,int pre)
{
    int x=u,y;
    vis[u]=true;
    for(int i: adj[u])
    {
        int v=u^a[i]^b[i];
        int w=t[i];
        if (v==pre) continue;
        dep[v]=dep[u]+w;
        y=dfs(v,u);
        if (dep[y]>dep[x]) x=y;
    }
    return x;
}
vector<int> L;
bool ok=0;
void dfs1(int u,int pre,int aim)
{
    L.pb(u);
    if (u==aim) ok=1;
    if (ok) return;
    for(int i: adj[u])
    {
        int v=u^a[i]^b[i];
        int w=t[i];
        if (v==pre) continue;
        dfs1(v,u,aim);
        if (ok) return;
    }
    L.pop_back();
}
int Find_diameter(int u)
{
    dep[u]=0;
    u=dfs(u,u);
    dep[u]=0;
    int v=dfs(u,u);
    g=max(g,dep[v]);
//    cerr<< "wtf "<<v<<'\n';
    ok=0;
    L.clear();
    dfs1(u,u,v);
//    for(int kz:L) cerr<< "ad "<<kz<<' '<<dep[kz]<<' '<<dep[v]-dep[kz]<<'\n';
    if (L.size()==1) return 0;
    for1(i,0,L.size()-2)
    {
//        cerr<<  "clmm "<<L[i]<<'\n';
        int x1=max(dep[L[i]],dep[v]-dep[L[i]]);
        int x2=max(dep[L[i+1]],dep[v]-dep[L[i+1]]);
        if (x2>=x1) return x1;
    }
}
vector<int> Lis;
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
    for1(i,1,m)
    {
        a[i]=A[i-1]+1;
        b[i]=B[i-1]+1;
        t[i]=T[i-1];
    }
    for1(i,1,m)
    {
        adj[a[i]].pb(i);
        adj[b[i]].pb(i);
//        cerr<< a[i]<<' '<<b[i]<<' '<<t[i]<<'\n';
    }
//    return 2;
    for1(i,1,n)
    {

        if (!vis[i])
        {
            int x=Find_diameter(i);
//            cerr<< i<<' '<<x<<'\n';
            Lis.pb(x);
        }
    }
//    for(int v:Lis) cerr<< v<<'\n';
    sort(all(Lis),greater<int>());
    if (Lis.size()==1)
    {
        return max(g,Lis[0]);
    }
    else if (Lis.size()==2)
    {
        return max(g,Lis[0]+Lis[1]+l);
    }
    else
    {
        return max(g,max(Lis[0]+Lis[1]+l,Lis[1]+Lis[2]+2*l));
    }
//return 42;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int, int)':
dreaming.cpp:58:13: warning: unused variable 'w' [-Wunused-variable]
   58 |         int w=t[i];
      |             ^
dreaming.cpp: In function 'int Find_diameter(int)':
dreaming.cpp:9:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define for1(i,j,k) for(int i=(j);i<=(k);i++)
      |                                    ^
dreaming.cpp:78:5: note: in expansion of macro 'for1'
   78 |     for1(i,0,L.size()-2)
      |     ^~~~
dreaming.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
   85 | }
      | ^

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