oj.uz

Submission #805115

# Submission time Handle Problem Language Result Execution time Memory
805115 2023-08-03T13:09:47 Z YassirSalama Dreaming (IOI13_dreaming) C++17
0 / 100
 17 ms 4016 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define pb push_back
#define F first
#define S second
const int MAXN=5000;
int n,m,l;
vector<vector<pair<int,int>>> v(MAXN);
vector<int> roots;
vector<vector<int>> diameters;
bool visited[MAXN];
int parr[MAXN];
int depth[MAXN];
pair<int,int> dfs(int node,int par,ll ew=0){//depth, best node
    visited[node]=true;
    parr[node]=par;
    depth[node]=ew;
    if(v[node].size()==1&&v[node][0].F==par){
        return {ew,node};
    }
    int ans=0;
    int best=0;
    for(auto x:v[node]){
        if(x.F!=par){
            pair<int,int> p=dfs(x.F,node,ew+x.S);
            if(p.F>ans){
                ans=p.F;
                best=p.S;
            }
        }
    }
    return {ans,best};
}
int bigdia=0;
void find_diameter(int node){
    pair<int,int> p=dfs(node,node);
    int f=p.S;
    memset(parr,-1,sizeof(parr));
    p=dfs(p.S,p.S);
    // dbg(f,p.S);
    vector<int> dia;
    while(p.S!=parr[p.S]) {
        dia.push_back(p.S);
        p.S=parr[p.S];
    }
    dia.push_back(p.S);
    reverse(all(dia));
    diameters.push_back(dia);
    bigdia=p.F;
}
struct Edge{
    int a,b,c;
    bool operator < (const Edge& other) const{
        return c<other.c;
    }
};
int par[MAXN];
int find(int node){
    if(node==par[node]) return node;
    return par[node]=find(par[node]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    l=L;
    memset(visited,false,sizeof(visited));
    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    memset(depth,0,sizeof(depth));
    for(int i=0;i<n;i++){
        if(!visited[i]){
            find_diameter(i);
        }
    }
    vector<Edge> edges;
    int d=diameters.size();
    set<pair<int,int>> p;
    for(int i=0;i+1<d;i++){
        for(auto x:diameters[i]){
            for(auto y:diameters[i+1]){
                if(p.find({x,y})!=p.end()) continue;
                int a,b,c,e;
                a=depth[diameters[i].back()]-depth[x];
                b=depth[x];
                c=depth[diameters[i+1].back()]-depth[y];
                e=depth[y];
                int cc=max(a,b);
                int dd=max(c,e);
                p.insert({x,y});
                p.insert({y,x});
                edges.push_back({.a=x,.b=y,.c=cc+l+dd});
            }
        }
    }
    sort(all(edges));
    for(int i=0;i<n;i++) par[i]=i;
    for(auto x:diameters){
        for(auto y:x) {
            par[y]=x[0];
        }
    }
    for(auto& edge:edges){
        if(find(edge.a)==find(edge.b)) continue;
        int a=find(edge.a);
        int b=find(edge.b);
        par[b]=a;
        // dbg(a,b,edge.a,edge.b);
        v[edge.a].pb({edge.b,l});
        v[edge.b].pb({edge.a,l});
    }
    find_diameter(0);
    // OVL(diameters.back()," ")
    return bigdia;
}

#ifdef IOI

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {
    int N, M, L, i;
    int res;

    FILE *f = fopen("dreaming.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d%d%d", &N, &M, &L);
    for (i = 0; i < M; i++)
        res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
    fclose(f);

    int answer = travelTime(N, M, L, A, B, T);
    printf("%d\n", answer);

    return 0;
}

#endif

Compilation message

dreaming.cpp: In function 'void find_diameter(int)':
dreaming.cpp:44:9: warning: unused variable 'f' [-Wunused-variable]
   44 |     int f=p.S;
      |         ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 428 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Incorrect 0 ms 468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 428 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Incorrect 0 ms 468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -