oj.uz

Submission #432796

# Submission time Handle Problem Language Result Execution time Memory
432796 2021-06-18T13:25:18 Z TryMax Stations (IOI20_stations) C++17
0 / 100
 78 ms 95624 KB 
#include "stations.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "stub.cpp"
#endif // LOCAL

#define f first
#define s second
#define pb push_back

using namespace std;

const int N = 2e6 + 10;

int sz[N], p[N], timer, was[N];
vector<int> a[N];

int cypher(int a, int b){
    return a * 1000 + (b - 1);
}

pair<int, int> decyper(int num){
    return {num / 1000, num % 1000 + 1};
}

void dfs(int u, int pr){
//    sz[u] = 1;
//    p[u] = timer++;
    for(auto v : a[u])
        if(pr != v){
            dfs(v, u);
//            sz[u] += sz[v];
        }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
//    vector<int> lb;
//    lb.resize(n);
    for(int i = 0; i < n - 1; ++i){
        a[u[i]].pb(v[i]);
        a[v[i]].pb(u[i]);
    }
    dfs(0, -1);
//    for(int i = 0; i < n; ++i)
//        if(was[i] == 0)
//            exit(1);
//    for(int i = 0; i < n; ++i)
//        lb[i] = cypher(p[i], sz[i]);
//    return lb;
}

int find_next_station(int s, int t, vector<int> c) {
    pair<int, int> s1 = decyper(s);
    pair<int, int> t1 = decyper(t);
    int pr = 0;
    vector<pair<int, int>> p;
    for(auto v : c){
        pair<int, int> c1 = decyper(v);
        if(c1.f <= s1.f)
            pr = v;
        p.pb(c1);
    }
    sort(p.begin(), p.end());
//    cout << s1.f << " " << s1.s << endl;
//    cout << t1.f << " " << t1.s << endl;
    if(t1.f < s1.f || t1.f >= s1.f + s1.s)
        return pr;
//    cout << 1 << endl;
    for(int i = p.size() - 1; i >= 0; --i)
        if(t1.f >= p[i].f)
            return cypher(p[i].f, p[i].s);
    return cypher(p[0].f, p[0].s);
}
/*
1
7 1000000
0 1
0 2
1 3
1 4
2 5
2 6
2
2 0 1
1 3 2

9
1
3

*/

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:50:1: warning: no return statement in function returning non-void [-Wreturn-type]
   50 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 61.0

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