oj.uz

Submission #736125

# Submission time Handle Problem Language Result Execution time Memory
736125 2023-05-05T08:54:03 Z onlk97 Stations (IOI20_stations) C++14
0 / 100
 937 ms 652 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> g[1010];
int fa[1010],sz[1010],hson[1010];
void dfs1(int cur,int prv){
    fa[cur]=prv;
    sz[cur]=1;
    int mxz=-1;
    for (int i:g[cur]){
        if (i==prv) continue;
        dfs1(i,cur);
        if (sz[i]>mxz){
            mxz=sz[i];
            hson[cur]=i;
        }
    }
}
int id[1010];
int curidx;
void dfs2(int cur){
    curidx++;
    id[cur]=curidx;
    if (!hson[cur]) return;
    dfs2(hson[cur]);
    for (int i:g[cur]){
        if (i!=fa[cur]&&i!=hson[cur]) dfs2(i);
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for (int i=0; i<=n; i++){
        fa[i]=0; sz[i]=0; hson[i]=0;
        g[i].clear(); id[i]=0;
    }
    curidx=0;
	for (int i=0; i<n-1; i++){
        g[u[i]+1].push_back(v[i]+1);
        g[v[i]+1].push_back(u[i]+1);
    }
    dfs1(1,0);
    dfs2(1);
    vector <int> ans(n);
    for (int i=0; i<n; i++) ans[i]=id[i+1];
    return ans;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for (int i:c){
        if (i==t) return t;
    }
    if (t<s){
        for (int i:c){
            if (i<s) return i;
        }
    }
    int mx=-1;
    for (int i:c){
        if (i<t) mx=max(mx,i);
    }
    return mx;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 542 ms 536 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 402 ms 528 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 615 ms 652 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 520 KB Output is correct
2 Correct 594 ms 532 KB Output is correct
3 Incorrect 618 ms 544 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 546 ms 640 KB Wrong query response.
2 Halted 0 ms 0 KB -