oj.uz

Submission #404320

# Submission time Handle Problem Language Result Execution time Memory
404320 2021-05-14T07:37:56 Z AmineTrabelsi Stations (IOI20_stations) C++14
10 / 100
 1069 ms 656 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 1010;
int timer = 0;
int tin[Mx],tout[Mx];
void dfs(int node,int par,vector<int> &labels,vector<vector<int>> &tr){
    tin[node] = timer++;
    for(auto i:tr[node]){
        if(i != par){
            dfs(i,node,labels,tr);
        }
    }
    tout[node] = timer++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<int> labels(n);
    vector<vector<int>> tr(n+1,vector<int>(0));
	for (int i = 0; i < n-1; i++) {
		tr[u[i]].push_back(v[i]);
        tr[v[i]].push_back(u[i]);
	}
    dfs(0,-1,labels,tr);
    for(int i=0;i<n;i++){
        labels[i] = tin[i]+tout[i]*1000;
    }
	return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    int s_tin = s%1000, s_tout = s/1000;
    int t_tin = t%1000, t_tout = t%1000;
    // going from s to t
    // if s,t not in each other subtree return c.back()
    if(s_tin >= t_tin && s_tout <= t_tout){
        return c.back();
    }
    if(t_tin >= s_tin && t_tout <= s_tout){
        for(auto p:c){
            int p_tin = p%1000, p_tout = p/1000;
            if(t_tin >= p_tin && t_tout <= p_tout){
                return p;
            }
        }
    }
    return c.back();
}
// c sorted
// small c deeper in the tree
// big c high in tree
// last c is parent

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 436 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=19000
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 288 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1991000
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 412 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=0, label=1997004
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 400 KB Output is correct
2 Correct 829 ms 400 KB Output is correct
3 Correct 643 ms 400 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 6 ms 476 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 834 ms 488 KB Output is correct
8 Correct 1069 ms 480 KB Output is correct
9 Correct 801 ms 480 KB Output is correct
10 Correct 696 ms 400 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 557 ms 488 KB Output is correct
17 Correct 601 ms 484 KB Output is correct
18 Correct 715 ms 484 KB Output is correct
19 Correct 643 ms 488 KB Output is correct
20 Correct 683 ms 488 KB Output is correct

Subtask #5
0 / 61.0

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