oj.uz

Submission #311980

# Submission time Handle Problem Language Result Execution time Memory
311980 2020-10-12T05:38:22 Z MonkeyKing Stations (IOI20_stations) C++14
100 / 100
 916 ms 1280 KB 
#include <bits/stdc++.h>
#include "stations.h"
#define all(x) x.begin(),x.end()
using namespace std;
vector <int> edges[1005];
int dfn;

void dfs(int x,int depth,int par,vector <int> &res)
{
    if(depth & 1)
    {
        res[x]=dfn++;
        for(auto u:edges[x])
        {
            if(u==par) continue;
            dfs(u,depth+1,x,res);
        }
    }
    else
    {
        for(auto u:edges[x])
        {
            if(u==par) continue;
            dfs(u,depth+1,x,res);
        }
        res[x]=dfn++;
    }
}

vector <int> label(int n,int k,vector <int> _ea,vector <int> _eb)
{
	dfn=0;
	assert((int)_ea.size()==n-1);
    vector <int> res;
    res.resize(n);
    for(int i=0;i<n;i++)
    {
    	edges[i].clear();
	}
    for(int i=0;i<n-1;i++)
    {
        edges[_ea[i]].push_back(_eb[i]);
        edges[_eb[i]].push_back(_ea[i]);
    }
    dfs(0,0,-1,res);
    return res;
}

int find_next_station(int s,int t,vector <int> c)
{
//	return 0;
    if(s>c[0]) // ºó¸ù
    {
        sort(all(c));
        int par=*c.begin();
        c.erase(c.begin());
        if(c.empty()) return par;
        if(t<c.front() || t>=s) return par;
        reverse(all(c));
        for(auto x:c)
        {
            if(t>=x) return x;
        }
    }
    else // Ïȸù
    {
        sort(all(c));
        int par=*(--c.end());
        c.erase(--c.end());
        if(c.empty()) return par;
        if(t>c.back() || t<=s) return par;
        for(auto x:c)
        {
            if(t<=x) return x;
        }
    }
    // assert(false);
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 1256 KB Output is correct
2 Correct 463 ms 1280 KB Output is correct
3 Correct 858 ms 876 KB Output is correct
4 Correct 657 ms 768 KB Output is correct
5 Correct 595 ms 880 KB Output is correct
6 Correct 489 ms 1024 KB Output is correct
7 Correct 468 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 828 KB Output is correct
2 Correct 521 ms 956 KB Output is correct
3 Correct 897 ms 872 KB Output is correct
4 Correct 679 ms 888 KB Output is correct
5 Correct 602 ms 880 KB Output is correct
6 Correct 450 ms 828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 1024 KB Output is correct
2 Correct 457 ms 1024 KB Output is correct
3 Correct 916 ms 884 KB Output is correct
4 Correct 651 ms 876 KB Output is correct
5 Correct 570 ms 1128 KB Output is correct
6 Correct 464 ms 1240 KB Output is correct
7 Correct 467 ms 772 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 4 ms 880 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 576 ms 876 KB Output is correct
12 Correct 538 ms 1252 KB Output is correct
13 Correct 532 ms 1008 KB Output is correct
14 Correct 456 ms 832 KB Output is correct
15 Correct 57 ms 872 KB Output is correct
16 Correct 67 ms 768 KB Output is correct
17 Correct 111 ms 812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 768 KB Output is correct
2 Correct 658 ms 880 KB Output is correct
3 Correct 583 ms 876 KB Output is correct
4 Correct 1 ms 880 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 590 ms 768 KB Output is correct
8 Correct 891 ms 896 KB Output is correct
9 Correct 671 ms 880 KB Output is correct
10 Correct 605 ms 768 KB Output is correct
11 Correct 7 ms 880 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 4 ms 888 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 1 ms 880 KB Output is correct
16 Correct 478 ms 876 KB Output is correct
17 Correct 489 ms 884 KB Output is correct
18 Correct 492 ms 884 KB Output is correct
19 Correct 509 ms 880 KB Output is correct
20 Correct 502 ms 872 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 1024 KB Output is correct
2 Correct 485 ms 1024 KB Output is correct
3 Correct 876 ms 876 KB Output is correct
4 Correct 675 ms 768 KB Output is correct
5 Correct 592 ms 876 KB Output is correct
6 Correct 500 ms 1280 KB Output is correct
7 Correct 516 ms 784 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 880 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 471 ms 812 KB Output is correct
12 Correct 569 ms 828 KB Output is correct
13 Correct 874 ms 1048 KB Output is correct
14 Correct 743 ms 876 KB Output is correct
15 Correct 617 ms 1008 KB Output is correct
16 Correct 480 ms 832 KB Output is correct
17 Correct 637 ms 672 KB Output is correct
18 Correct 475 ms 896 KB Output is correct
19 Correct 477 ms 1024 KB Output is correct
20 Correct 478 ms 832 KB Output is correct
21 Correct 60 ms 768 KB Output is correct
22 Correct 96 ms 840 KB Output is correct
23 Correct 109 ms 768 KB Output is correct
24 Correct 6 ms 872 KB Output is correct
25 Correct 6 ms 872 KB Output is correct
26 Correct 5 ms 876 KB Output is correct
27 Correct 4 ms 896 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 563 ms 876 KB Output is correct
30 Correct 595 ms 872 KB Output is correct
31 Correct 569 ms 1004 KB Output is correct
32 Correct 581 ms 768 KB Output is correct
33 Correct 519 ms 876 KB Output is correct
34 Correct 359 ms 1016 KB Output is correct
35 Correct 436 ms 1024 KB Output is correct
36 Correct 472 ms 1136 KB Output is correct
37 Correct 464 ms 904 KB Output is correct
38 Correct 499 ms 992 KB Output is correct
39 Correct 446 ms 772 KB Output is correct
40 Correct 581 ms 896 KB Output is correct
41 Correct 559 ms 768 KB Output is correct
42 Correct 65 ms 828 KB Output is correct
43 Correct 114 ms 824 KB Output is correct
44 Correct 136 ms 768 KB Output is correct
45 Correct 163 ms 768 KB Output is correct
46 Correct 377 ms 768 KB Output is correct
47 Correct 434 ms 768 KB Output is correct
48 Correct 86 ms 784 KB Output is correct
49 Correct 71 ms 1024 KB Output is correct