oj.uz

Submission #1079538

# Submission time Handle Problem Language Result Execution time Memory
1079538 2024-08-28T16:29:23 Z anango Stations (IOI20_stations) C++17
72.5094 / 100
 642 ms 1268 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define cout cerr


vector<vector<int>> adjlist;

vector<int> depth;
vector<int> tin;
vector<int> tout;
int tim = 0;

void dfs(int node, int par) {
    tin[node] = tim++;
    for (int j:adjlist[node]) {
        if (j!=par) {
            depth[j] = depth[node]+1;
            dfs(j,node);
        }
    }
    tout[node] = tim++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    tim = 0;
	std::vector<int> labels(n);
    adjlist=vector<vector<int>>(n);
    tin=tout=vector<int>(n,-1);
    depth=vector<int>(n,0);
    for (int i=0; i<n-1; i++) {
        adjlist[u[i]].push_back(v[i]);
        adjlist[v[i]].push_back(u[i]);
    }
    dfs(0,-1);
	for (int i = 0; i < n; i++) {
        if (depth[i]%2==1) {
		    labels[i] = tin[i];
        }
        else {
            labels[i] = 3000+tout[i];
        }
        //cout << i << " " << tin[i] <<" " << tout[i] <<" " << labels[i] << endl;
	}

    //consider using the euler tour trick on the tree
    //for each node, store the left and right times of its subtree in the label (using perfect hashing)
    //for a node, you know the tin and tout (call these inv and outv)
    //then for every child, you also know the tin and tout of that child (call these inc and outc)
    //and the tin and tout of the destination (call these ind and outd)
    //so you know that if inv<=ind<=outd<=outv, then the destination is in this subtree
    //and if inc<=ind<=outd<=outc for some child, the destination is in the subtree of this child
    //if none of these hold, then go up
    //this uses at most n^2 labels
    //we could just use in but then it jambloats because we don't know where the subtree ends
    //actually what about storing out for even depth
    //because we know one of the in values for child for free
    //and if we know out[node] we know one out value for free
    //that should work for 2000

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(c.begin(), c.end());

    //cout << "TRY FIND " << endl;
    for (auto i:c) {
        //cout << i <<" ";
    }
    //cout << endl;
    //cout << "DOING " << s <<" " << t << endl;
    if (t>=3000) {
        t-=3000;
    }
    if (s>=3000) {
        //depth is even
        s-=3000;
        //so all the children are in-values, our node is an out-value
        //the lowest in-value is actually the parent, so that can be ignored
        c.push_back(s+1);
        sort(c.begin(), c.end());
        //cout << s <<" " << c.size() << endl;
        for (auto i:c) {
            //cout << i <<" ";
            assert(i<3000);
        }
        //cout << endl;
        for (int i=2; i<c.size(); i++) {
            if (c[i-1]<=t && t<c[i]) {
                return c[i-1];
            }
        }
        return c[0];
    }
    else {
        //depth is odd
        for (int i=0; i<c.size(); i++) {
            c[i]-=3000;
        }
        //so all the children are out-values, our node is an in-value
        //max value is actually the parent
        c.push_back(s+1);
        sort(c.begin(), c.end());
        //assert(c.front()==s+1);
        ////cout << "DOCTORED C " << endl;
        for (auto i:c) {
            //cout << i <<" ";
        }
        //cout << endl;
        for (int i=1; i<((int)c.size())-1; i++) {
            if (c[i-1]<=t && t<=c[i]) {
                return c[i]+3000;
            }
        }
        return c.back()+3000;
    }
	return c[0];
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:69:15: warning: unused variable 'i' [-Wunused-variable]
   69 |     for (auto i:c) {
      |               ^
stations.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i=2; i<c.size(); i++) {
      |                       ~^~~~~~~~~
stations.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i=0; i<c.size(); i++) {
      |                       ~^~~~~~~~~
stations.cpp:108:19: warning: unused variable 'i' [-Wunused-variable]
  108 |         for (auto i:c) {
      |                   ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 940 KB Output is correct
2 Correct 344 ms 940 KB Output is correct
3 Correct 642 ms 684 KB Output is correct
4 Correct 468 ms 684 KB Output is correct
5 Correct 407 ms 776 KB Output is correct
6 Correct 338 ms 1196 KB Output is correct
7 Correct 318 ms 768 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 1 ms 772 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 373 ms 684 KB Output is correct
12 Correct 313 ms 1188 KB Output is correct
13 Correct 295 ms 1184 KB Output is correct
14 Correct 314 ms 684 KB Output is correct
15 Correct 51 ms 768 KB Output is correct
16 Correct 40 ms 684 KB Output is correct
17 Correct 72 ms 772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 692 KB Output is correct
2 Correct 464 ms 684 KB Output is correct
3 Correct 419 ms 684 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 426 ms 776 KB Output is correct
8 Correct 625 ms 684 KB Output is correct
9 Correct 459 ms 684 KB Output is correct
10 Correct 426 ms 684 KB Output is correct
11 Correct 3 ms 776 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 772 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 373 ms 944 KB Output is correct
17 Correct 340 ms 684 KB Output is correct
18 Correct 360 ms 684 KB Output is correct
19 Correct 362 ms 936 KB Output is correct
20 Correct 349 ms 684 KB Output is correct

Subtask #5
46.5094 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 376 ms 936 KB Partially correct
2 Partially correct 322 ms 940 KB Partially correct
3 Partially correct 628 ms 684 KB Partially correct
4 Partially correct 462 ms 684 KB Partially correct
5 Partially correct 404 ms 684 KB Partially correct
6 Partially correct 281 ms 940 KB Partially correct
7 Partially correct 296 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 2 ms 776 KB Partially correct
10 Partially correct 0 ms 776 KB Partially correct
11 Partially correct 315 ms 684 KB Partially correct
12 Partially correct 372 ms 684 KB Partially correct
13 Partially correct 599 ms 684 KB Partially correct
14 Partially correct 459 ms 684 KB Partially correct
15 Partially correct 452 ms 684 KB Partially correct
16 Partially correct 350 ms 688 KB Partially correct
17 Partially correct 418 ms 684 KB Partially correct
18 Partially correct 342 ms 1268 KB Partially correct
19 Partially correct 307 ms 940 KB Partially correct
20 Partially correct 334 ms 940 KB Partially correct
21 Partially correct 30 ms 772 KB Partially correct
22 Partially correct 46 ms 768 KB Partially correct
23 Partially correct 61 ms 688 KB Partially correct
24 Partially correct 3 ms 768 KB Partially correct
25 Partially correct 2 ms 772 KB Partially correct
26 Partially correct 2 ms 772 KB Partially correct
27 Partially correct 1 ms 768 KB Partially correct
28 Partially correct 0 ms 776 KB Partially correct
29 Partially correct 357 ms 684 KB Partially correct
30 Partially correct 326 ms 684 KB Partially correct
31 Partially correct 345 ms 684 KB Partially correct
32 Partially correct 355 ms 684 KB Partially correct
33 Partially correct 350 ms 684 KB Partially correct
34 Partially correct 271 ms 940 KB Partially correct
35 Partially correct 268 ms 1200 KB Partially correct
36 Partially correct 335 ms 1020 KB Partially correct
37 Partially correct 303 ms 1192 KB Partially correct
38 Partially correct 317 ms 780 KB Partially correct
39 Partially correct 299 ms 1024 KB Partially correct
40 Partially correct 317 ms 1020 KB Partially correct
41 Partially correct 312 ms 932 KB Partially correct
42 Partially correct 30 ms 768 KB Partially correct
43 Partially correct 73 ms 736 KB Partially correct
44 Partially correct 86 ms 684 KB Partially correct
45 Partially correct 96 ms 896 KB Partially correct
46 Partially correct 216 ms 688 KB Partially correct
47 Partially correct 221 ms 688 KB Partially correct
48 Partially correct 39 ms 908 KB Partially correct
49 Partially correct 31 ms 848 KB Partially correct