oj.uz

Submission #367302

# Submission time Handle Problem Language Result Execution time Memory
367302 2021-02-16T20:15:57 Z PurpleCrayon Stations (IOI20_stations) C++17
5 / 100
 1148 ms 1232 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())

int tt;
vector<int> ans;
vector<vector<int>> adj;

void dfs(int c=0, int p=-1, bool b=0){
    if (!b) ans[c] = tt++;
    for (auto nxt : adj[c]) if (nxt != p) dfs(nxt, c, b^1);
    if (b) ans[c] = tt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    ans.assign(n, -1), adj.assign(n, vector<int>()), tt=0;
    for (int i = 0; i < n-1; i++) 
        adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
    dfs();
    return ans;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s == 0){ //ans for the root
        for (auto nxt : c) if (nxt >= t) return nxt;
        assert(false);
    }
    bool b=s>c[0];

    if (b){ //i'm postorder
        int p = c[0];
        if (sz(c) == 1 || t < c[1] || t > s)
            return p; 
        
        int ans=-1;
        for (auto nxt : c) if (nxt != p) {
            if (nxt <= t) ans = nxt;
        }
        return ans;

    } else { //i'm preorder
        int p = c[sz(c)-1];
        if (sz(c) == 1 || t < s || t >= c[sz(c)-1]) 
            return p;

        int ans=-1;
        for (auto nxt : c) if (nxt != p) {
            if (nxt >= t){
                return nxt;
            }
        }
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:13: warning: unused variable 'ans' [-Wunused-variable]
   47 |         int ans=-1;
      |             ^~~
stations.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 956 KB Output is correct
2 Correct 484 ms 1072 KB Output is correct
3 Correct 1148 ms 868 KB Output is correct
4 Correct 719 ms 736 KB Output is correct
5 Correct 720 ms 756 KB Output is correct
6 Correct 450 ms 864 KB Output is correct
7 Correct 446 ms 864 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Correct 2 ms 756 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 884 KB Output is correct
2 Correct 550 ms 884 KB Output is correct
3 Correct 930 ms 868 KB Output is correct
4 Correct 678 ms 756 KB Output is correct
5 Correct 660 ms 868 KB Output is correct
6 Correct 536 ms 972 KB Output is correct
7 Correct 447 ms 864 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 5 ms 756 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 614 ms 868 KB Output is correct
12 Correct 529 ms 840 KB Output is correct
13 Incorrect 489 ms 864 KB Wrong query response.
14 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 884 KB Output is correct
2 Correct 734 ms 736 KB Output is correct
3 Correct 651 ms 868 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 4 ms 736 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 643 ms 848 KB Output is correct
8 Correct 1027 ms 864 KB Output is correct
9 Correct 682 ms 736 KB Output is correct
10 Correct 655 ms 756 KB Output is correct
11 Incorrect 7 ms 736 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 1232 KB Output is correct
2 Correct 447 ms 952 KB Output is correct
3 Correct 860 ms 884 KB Output is correct
4 Correct 616 ms 868 KB Output is correct
5 Correct 542 ms 868 KB Output is correct
6 Correct 421 ms 972 KB Output is correct
7 Correct 466 ms 864 KB Output is correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Correct 1 ms 796 KB Output is correct
11 Incorrect 469 ms 992 KB Wrong query response.
12 Halted 0 ms 0 KB -