oj.uz

Submission #306854

# Submission time Handle Problem Language Result Execution time Memory
306854 2020-09-26T11:09:24 Z nicolaalexandra Stations (IOI20_stations) C++14
100 / 100
 915 ms 1280 KB 
#include <bits/stdc++.h>
#include "stations.h"
#define DIM 1010
using namespace std;

vector <int> L[DIM],aux;
int viz[DIM],level[DIM],fth[DIM];
pair <int,int> poz[DIM];
int idx;

void dfs (int nod){

    viz[nod] = 1;
    poz[nod].first = ++idx;
    for (auto vecin : L[nod])
        if (!viz[vecin]){
            fth[vecin] = nod;
            level[vecin] = 1 + level[nod];
            dfs (vecin);
        }
    poz[nod].second = ++idx;
}

int cautare_binara (int n, int val){
    int st = 0, dr = n-1;
    while (st <= dr){
        int mid = (st + dr)>>1;
        if (aux[mid] == val)
            return mid;
        if (aux[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
}

vector <int> label (int n, int k, vector <int> u, vector <int> v){
    int i;

    for (i=0;i<n;i++)
        L[i].clear();

    for (i=0;i<n-1;i++){
        int x = u[i], y = v[i];
        L[x].push_back(y);
        L[y].push_back(x);
    }

    memset (viz,0,sizeof viz);
    memset (level,0,sizeof level);
    memset (poz,0,sizeof poz);
    memset (fth,0,sizeof fth);

    idx = -1;

    dfs (0);

    vector <int> labels;
    for (i=0;i<n;i++){
        if (level[i] % 2 == 0)
            labels.push_back(poz[i].first);
        else labels.push_back(poz[i].second);
    }

    /// pot sa le normalizez??
    aux = labels;
    sort (aux.begin(),aux.end());
    for (i=0;i<n;i++)
        labels[i] = cautare_binara (n,labels[i]);

    return labels;

}

int find_next_station (int x, int y, vector <int> v){

    /// mai intai vad daca se afla pe un nivel par sau impar

    int ok = 0;
    for (auto it : v)
        if (it < x){
            ok = 1;
            break;
        }

    if (!ok){ /// labelul x inseamna de fapt un inceput de interval

        if (y < x)
            return v.back();

        for (auto it : v)
            if (y <= it)
                return it;

        return v.back();

    } else {

        if (y > x)
            return v.front();

        for (int i=v.size()-1;i>=0;i--)
            if (y >= v[i])
                return v[i];

        return v.front();
    }

}

Compilation message

stations.cpp: In function 'int cautare_binara(int, int)':
stations.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 1008 KB Output is correct
2 Correct 450 ms 1008 KB Output is correct
3 Correct 859 ms 768 KB Output is correct
4 Correct 719 ms 860 KB Output is correct
5 Correct 610 ms 768 KB Output is correct
6 Correct 498 ms 1024 KB Output is correct
7 Correct 529 ms 900 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 788 KB Output is correct
2 Correct 552 ms 768 KB Output is correct
3 Correct 915 ms 856 KB Output is correct
4 Correct 679 ms 856 KB Output is correct
5 Correct 646 ms 768 KB Output is correct
6 Correct 421 ms 796 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 1024 KB Output is correct
2 Correct 491 ms 1024 KB Output is correct
3 Correct 883 ms 768 KB Output is correct
4 Correct 642 ms 1024 KB Output is correct
5 Correct 615 ms 1040 KB Output is correct
6 Correct 440 ms 1024 KB Output is correct
7 Correct 449 ms 780 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 577 ms 856 KB Output is correct
12 Correct 445 ms 1116 KB Output is correct
13 Correct 466 ms 1128 KB Output is correct
14 Correct 439 ms 768 KB Output is correct
15 Correct 53 ms 864 KB Output is correct
16 Correct 70 ms 928 KB Output is correct
17 Correct 113 ms 792 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 768 KB Output is correct
2 Correct 773 ms 860 KB Output is correct
3 Correct 637 ms 768 KB Output is correct
4 Correct 3 ms 996 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 601 ms 768 KB Output is correct
8 Correct 851 ms 856 KB Output is correct
9 Correct 640 ms 860 KB Output is correct
10 Correct 598 ms 768 KB Output is correct
11 Correct 6 ms 864 KB Output is correct
12 Correct 6 ms 1024 KB Output is correct
13 Correct 6 ms 868 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 510 ms 768 KB Output is correct
17 Correct 490 ms 856 KB Output is correct
18 Correct 497 ms 856 KB Output is correct
19 Correct 498 ms 852 KB Output is correct
20 Correct 525 ms 1024 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 1024 KB Output is correct
2 Correct 614 ms 1280 KB Output is correct
3 Correct 904 ms 860 KB Output is correct
4 Correct 645 ms 860 KB Output is correct
5 Correct 687 ms 1040 KB Output is correct
6 Correct 499 ms 1024 KB Output is correct
7 Correct 448 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 480 ms 768 KB Output is correct
12 Correct 643 ms 768 KB Output is correct
13 Correct 862 ms 852 KB Output is correct
14 Correct 680 ms 832 KB Output is correct
15 Correct 620 ms 852 KB Output is correct
16 Correct 438 ms 808 KB Output is correct
17 Correct 590 ms 860 KB Output is correct
18 Correct 520 ms 1024 KB Output is correct
19 Correct 546 ms 1024 KB Output is correct
20 Correct 450 ms 808 KB Output is correct
21 Correct 54 ms 768 KB Output is correct
22 Correct 74 ms 896 KB Output is correct
23 Correct 106 ms 792 KB Output is correct
24 Correct 7 ms 768 KB Output is correct
25 Correct 5 ms 868 KB Output is correct
26 Correct 5 ms 860 KB Output is correct
27 Correct 4 ms 860 KB Output is correct
28 Correct 2 ms 868 KB Output is correct
29 Correct 509 ms 868 KB Output is correct
30 Correct 533 ms 860 KB Output is correct
31 Correct 600 ms 860 KB Output is correct
32 Correct 572 ms 864 KB Output is correct
33 Correct 494 ms 768 KB Output is correct
34 Correct 317 ms 1024 KB Output is correct
35 Correct 497 ms 1008 KB Output is correct
36 Correct 453 ms 1120 KB Output is correct
37 Correct 445 ms 1008 KB Output is correct
38 Correct 491 ms 1024 KB Output is correct
39 Correct 470 ms 1008 KB Output is correct
40 Correct 513 ms 1144 KB Output is correct
41 Correct 444 ms 888 KB Output is correct
42 Correct 75 ms 800 KB Output is correct
43 Correct 109 ms 788 KB Output is correct
44 Correct 149 ms 1024 KB Output is correct
45 Correct 166 ms 768 KB Output is correct
46 Correct 319 ms 768 KB Output is correct
47 Correct 317 ms 1040 KB Output is correct
48 Correct 66 ms 1024 KB Output is correct
49 Correct 67 ms 1024 KB Output is correct