oj.uz

Submission #422615

# Submission time Handle Problem Language Result Execution time Memory
422615 2021-06-10T09:14:12 Z TLP39 Stations (IOI20_stations) C++14
100 / 100
 1016 ms 776 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[1003];
int par[1003]={};
int si[1003]={};
int lab[1003];

void dfs(int v)
{
    si[v]=1;
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par[v]) continue;
        par[adj[v][i]]=v;
        dfs(adj[v][i]);
        si[v]+=si[adj[v][i]];
    }
}

void getlabel(int v,int st,int ed)
{
    lab[v]=st;
    if(st==ed) return;
    int x=st,y;
    if(st<ed)
    {
        for(int i=0;i<adj[v].size();i++)
        {
            if(adj[v][i]==par[v]) continue;
            y=x+1;
            x+=si[adj[v][i]];
            getlabel(adj[v][i],x,y);
        }
        return;
    }
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i]==par[v]) continue;
        y=x-1;
        x-=si[adj[v][i]];
        getlabel(adj[v][i],x,y);
    }
    return;
}

std::vector<int> label(int N, int k, std::vector<int> u, std::vector<int> v) {
    for(int i=0;i<=n;i++) adj[i].clear();
    n=N;
	std::vector<int> labels(N);
	par[0]=-1;
	for(int i=0;i<n-1;i++)
	{
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
	}
	dfs(0);
	getlabel(0,0,n-1);
	for(int i=0;i<n;i++) labels[i]=lab[i];
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(c.size()==1) return c[0];
	if(s==0)
	{
        for(int i=0;i<c.size();i++)
        {
            if(c[i]>=t) return c[i];
        }
	}
	if(c[0]<s)
	{
        if(t>s || t<c[1]) return c[0];
        for(int i=c.size()-1;i>0;i--)
        {
            if(c[i]<=t) return c[i];
        }
	}
	int ss=c.size()-1;
	if(t<s || t>c[ss-1]) return c[ss];
	for(int i=0;i<ss;i++)
	{
        if(t<=c[i]) return c[i];
	}
	return -1;
}

Compilation message

stations.cpp: In function 'void dfs(int)':
stations.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
stations.cpp: In function 'void getlabel(int, int, int)':
stations.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i=0;i<adj[v].size();i++)
      |                     ~^~~~~~~~~~~~~~
stations.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 516 KB Output is correct
2 Correct 517 ms 636 KB Output is correct
3 Correct 954 ms 420 KB Output is correct
4 Correct 634 ms 400 KB Output is correct
5 Correct 684 ms 404 KB Output is correct
6 Correct 476 ms 504 KB Output is correct
7 Correct 474 ms 524 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 508 KB Output is correct
2 Correct 562 ms 528 KB Output is correct
3 Correct 949 ms 400 KB Output is correct
4 Correct 836 ms 400 KB Output is correct
5 Correct 638 ms 528 KB Output is correct
6 Correct 494 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 644 KB Output is correct
2 Correct 439 ms 528 KB Output is correct
3 Correct 1016 ms 644 KB Output is correct
4 Correct 781 ms 516 KB Output is correct
5 Correct 572 ms 404 KB Output is correct
6 Correct 467 ms 528 KB Output is correct
7 Correct 413 ms 512 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 642 ms 400 KB Output is correct
12 Correct 567 ms 648 KB Output is correct
13 Correct 439 ms 628 KB Output is correct
14 Correct 489 ms 520 KB Output is correct
15 Correct 64 ms 596 KB Output is correct
16 Correct 80 ms 528 KB Output is correct
17 Correct 113 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 512 KB Output is correct
2 Correct 715 ms 400 KB Output is correct
3 Correct 668 ms 528 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 622 ms 516 KB Output is correct
8 Correct 1015 ms 544 KB Output is correct
9 Correct 790 ms 528 KB Output is correct
10 Correct 657 ms 528 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 563 ms 536 KB Output is correct
17 Correct 636 ms 544 KB Output is correct
18 Correct 591 ms 548 KB Output is correct
19 Correct 618 ms 532 KB Output is correct
20 Correct 579 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 612 KB Output is correct
2 Correct 544 ms 528 KB Output is correct
3 Correct 906 ms 504 KB Output is correct
4 Correct 696 ms 528 KB Output is correct
5 Correct 618 ms 528 KB Output is correct
6 Correct 573 ms 528 KB Output is correct
7 Correct 528 ms 520 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 547 ms 508 KB Output is correct
12 Correct 621 ms 568 KB Output is correct
13 Correct 829 ms 528 KB Output is correct
14 Correct 786 ms 400 KB Output is correct
15 Correct 666 ms 516 KB Output is correct
16 Correct 534 ms 512 KB Output is correct
17 Correct 763 ms 516 KB Output is correct
18 Correct 596 ms 628 KB Output is correct
19 Correct 512 ms 596 KB Output is correct
20 Correct 487 ms 508 KB Output is correct
21 Correct 49 ms 548 KB Output is correct
22 Correct 69 ms 528 KB Output is correct
23 Correct 111 ms 656 KB Output is correct
24 Correct 7 ms 604 KB Output is correct
25 Correct 6 ms 468 KB Output is correct
26 Correct 6 ms 476 KB Output is correct
27 Correct 4 ms 628 KB Output is correct
28 Correct 2 ms 604 KB Output is correct
29 Correct 564 ms 512 KB Output is correct
30 Correct 608 ms 528 KB Output is correct
31 Correct 537 ms 536 KB Output is correct
32 Correct 545 ms 528 KB Output is correct
33 Correct 609 ms 512 KB Output is correct
34 Correct 397 ms 520 KB Output is correct
35 Correct 452 ms 652 KB Output is correct
36 Correct 458 ms 616 KB Output is correct
37 Correct 538 ms 628 KB Output is correct
38 Correct 565 ms 656 KB Output is correct
39 Correct 555 ms 776 KB Output is correct
40 Correct 498 ms 756 KB Output is correct
41 Correct 564 ms 632 KB Output is correct
42 Correct 74 ms 528 KB Output is correct
43 Correct 104 ms 656 KB Output is correct
44 Correct 177 ms 528 KB Output is correct
45 Correct 170 ms 528 KB Output is correct
46 Correct 332 ms 528 KB Output is correct
47 Correct 350 ms 528 KB Output is correct
48 Correct 69 ms 676 KB Output is correct
49 Correct 72 ms 656 KB Output is correct