oj.uz

Submission #415634

# Submission time Handle Problem Language Result Execution time Memory
415634 2021-06-01T09:59:06 Z MKopchev Stations (IOI20_stations) C++14
100 / 100
 1238 ms 900 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e3+42;

vector<int> adj[nmax];

int in[nmax],out[nmax],when;

vector<int> outp;

void dfs(int node,int par,int depth)
{
    when++;

    in[node]=when;

    for(auto w:adj[node])
        if(w!=par)dfs(w,node,depth+1);

    when++;

    out[node]=when;

    //cout<<node<<" "<<depth<<" -> "<<in[node]<<" "<<out[node]<<endl;

    if(depth%2==0)outp[node]=in[node];
    else outp[node]=out[node];
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	outp={};
	for(int i=0;i<n;i++)adj[i]={},outp.push_back(0);
	when=0;

	for(int i=0;i<n-1;i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

	dfs(0,0,0);

	//for(auto w:outp)cout<<w<<" ";cout<<endl;

	vector<int> sorted=outp;
	sort(sorted.begin(),sorted.end());

	for(auto &w:outp)
        w=lower_bound(sorted.begin(),sorted.end(),w)-sorted.begin();

	return outp;
}

int find_next_station(int s, int t, std::vector<int> c) {

	for(auto w:c)
        if(w==t)return w;

    sort(c.begin(),c.end());

    if(c.size()==1)return c[0];

    //cout<<"s= "<<s<<" t= "<<t<<" c= ";for(auto w:c)cout<<w<<" ";cout<<endl;

	if(s<c[0])
    {
        vector<int> c_in={s+1};
        vector<int> c_out=c;

        c_out.pop_back();

        for(int i=1;i<c_out.size();i++)
            c_in.push_back(c_out[i-1]+1);

        for(int i=0;i<c_in.size();i++)
            if(c_in[i]<=t&&t<=c_out[i])return c[i];

        return c.back();
    }
        vector<int> c_in=c;
        vector<int> c_out={};

        c_in.erase(c_in.begin(),c_in.begin()+1);

        for(int i=0;i+1<c_in.size();i++)
            c_out.push_back(c_in[i+1]-1);

        c_out.push_back(s-1);

        /*
        cout<<"c_in: ";for(auto w:c_in)cout<<w<<" ";cout<<endl;
        cout<<"c_out: ";for(auto w:c_out)cout<<w<<" ";cout<<endl;
        */

        for(int i=0;i<c_in.size();i++)
            if(c_in[i]<=t&&t<=c_out[i])return c[i+1];

        return c[0];
}
/*
static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;

int main() {
	assert(scanf("%d", &r) == 1);
	for (int tc = 0; tc < r; tc++) {
		assert(scanf("%d%d", &n, &k) == 2);
		u.resize(n - 1);
		v.resize(n - 1);
		adjlist.clear();
		adjlist.resize(n);
		for (int i = 0; i < n - 1; i++) {
			assert(scanf("%d%d", &u[i], &v[i]) == 2);
			adjlist[u[i]].push_back(v[i]);
			adjlist[v[i]].push_back(u[i]);
		}
		labels = label(n, k, u, v);
		if ((int)labels.size() != n) {
			printf("Number of labels not equal to %d\n", n);
			exit(0);
		}
		reverse_labels.clear();
		for (int i = 0; i < n; i++) {
			if (labels[i] < 0 || labels[i] > k) {
				printf("Label not in range 0 to %d\n", k);
				exit(0);
			}
			if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				printf("Labels not unique\n");
				exit(0);
			}
			reverse_labels[labels[i]] = i;
			if (labels[i] > max_label) {
				max_label = labels[i];
			}
		}
		assert(scanf("%d", &q) == 1);
		for (int i = 0; i < q; i++) {
			assert(scanf("%d%d%d", &s, &t, &w) == 3);
			c.clear();
			for (int v : adjlist[s]) {
				c.push_back(labels[v]);
			}
			std::sort(c.begin(), c.end());
			int answer = find_next_station(labels[s], labels[t], c);
			if (!std::binary_search(c.begin(), c.end(), answer)) {
				printf("Label %d returned by find_next_station not found in c\n", answer);
				exit(0);
			}
			answers.push_back(reverse_labels[answer]);
		}
	}
	printf("%d\n", max_label);
	for (int index : answers) {
		printf("%d\n", index);
	}
	exit(0);
}
*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i=1;i<c_out.size();i++)
      |                     ~^~~~~~~~~~~~~
stations.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<c_in.size();i++)
      |                     ~^~~~~~~~~~~~
stations.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i=0;i+1<c_in.size();i++)
      |                     ~~~^~~~~~~~~~~~
stations.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i=0;i<c_in.size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 640 KB Output is correct
2 Correct 491 ms 628 KB Output is correct
3 Correct 1220 ms 400 KB Output is correct
4 Correct 995 ms 400 KB Output is correct
5 Correct 770 ms 400 KB Output is correct
6 Correct 546 ms 656 KB Output is correct
7 Correct 645 ms 516 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 8 ms 596 KB Output is correct
10 Correct 2 ms 464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 508 KB Output is correct
2 Correct 866 ms 632 KB Output is correct
3 Correct 949 ms 492 KB Output is correct
4 Correct 702 ms 400 KB Output is correct
5 Correct 636 ms 516 KB Output is correct
6 Correct 526 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 640 KB Output is correct
2 Correct 462 ms 632 KB Output is correct
3 Correct 1164 ms 400 KB Output is correct
4 Correct 871 ms 400 KB Output is correct
5 Correct 940 ms 404 KB Output is correct
6 Correct 577 ms 640 KB Output is correct
7 Correct 516 ms 656 KB Output is correct
8 Correct 5 ms 448 KB Output is correct
9 Correct 7 ms 420 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 756 ms 496 KB Output is correct
12 Correct 533 ms 760 KB Output is correct
13 Correct 491 ms 740 KB Output is correct
14 Correct 462 ms 568 KB Output is correct
15 Correct 55 ms 528 KB Output is correct
16 Correct 95 ms 544 KB Output is correct
17 Correct 117 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 400 KB Output is correct
2 Correct 827 ms 400 KB Output is correct
3 Correct 710 ms 528 KB Output is correct
4 Correct 6 ms 400 KB Output is correct
5 Correct 6 ms 448 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 786 ms 528 KB Output is correct
8 Correct 1238 ms 400 KB Output is correct
9 Correct 876 ms 528 KB Output is correct
10 Correct 713 ms 400 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 8 ms 476 KB Output is correct
13 Correct 6 ms 416 KB Output is correct
14 Correct 7 ms 400 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 572 ms 400 KB Output is correct
17 Correct 582 ms 400 KB Output is correct
18 Correct 564 ms 520 KB Output is correct
19 Correct 671 ms 400 KB Output is correct
20 Correct 572 ms 516 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 656 KB Output is correct
2 Correct 503 ms 520 KB Output is correct
3 Correct 1012 ms 400 KB Output is correct
4 Correct 658 ms 492 KB Output is correct
5 Correct 755 ms 400 KB Output is correct
6 Correct 649 ms 648 KB Output is correct
7 Correct 523 ms 528 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 3 ms 476 KB Output is correct
11 Correct 595 ms 540 KB Output is correct
12 Correct 739 ms 516 KB Output is correct
13 Correct 943 ms 656 KB Output is correct
14 Correct 742 ms 400 KB Output is correct
15 Correct 609 ms 520 KB Output is correct
16 Correct 607 ms 520 KB Output is correct
17 Correct 825 ms 496 KB Output is correct
18 Correct 578 ms 736 KB Output is correct
19 Correct 573 ms 900 KB Output is correct
20 Correct 660 ms 528 KB Output is correct
21 Correct 70 ms 528 KB Output is correct
22 Correct 92 ms 656 KB Output is correct
23 Correct 140 ms 656 KB Output is correct
24 Correct 5 ms 600 KB Output is correct
25 Correct 11 ms 468 KB Output is correct
26 Correct 8 ms 588 KB Output is correct
27 Correct 7 ms 476 KB Output is correct
28 Correct 5 ms 472 KB Output is correct
29 Correct 571 ms 520 KB Output is correct
30 Correct 565 ms 528 KB Output is correct
31 Correct 650 ms 400 KB Output is correct
32 Correct 760 ms 400 KB Output is correct
33 Correct 575 ms 400 KB Output is correct
34 Correct 336 ms 692 KB Output is correct
35 Correct 489 ms 772 KB Output is correct
36 Correct 575 ms 532 KB Output is correct
37 Correct 590 ms 656 KB Output is correct
38 Correct 613 ms 784 KB Output is correct
39 Correct 531 ms 700 KB Output is correct
40 Correct 578 ms 752 KB Output is correct
41 Correct 685 ms 856 KB Output is correct
42 Correct 90 ms 584 KB Output is correct
43 Correct 163 ms 672 KB Output is correct
44 Correct 150 ms 512 KB Output is correct
45 Correct 232 ms 528 KB Output is correct
46 Correct 387 ms 520 KB Output is correct
47 Correct 478 ms 592 KB Output is correct
48 Correct 85 ms 656 KB Output is correct
49 Correct 93 ms 656 KB Output is correct