oj.uz

Submission #307183

# Submission time Handle Problem Language Result Execution time Memory
307183 2020-09-27T09:56:41 Z FelixMP Stations (IOI20_stations) C++14
100 / 100
 985 ms 1196 KB 
    #include "stations.h"
    #include <vector>
    #include <algorithm>
    #include <utility>
    #include <iostream>
     
    using namespace std;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef pair<int, int> ii;
     
    vvi al;
    vi rans;
    int ft = 0;
     
    ii dfs(int v, int p, int r) {
     
    	int cmin =  1002;
    	int cmax = -1;
     
    	for(int i=0; i < (int)al[v].size(); ++i) {
    		int u = al[v][i];
    		if(u == p) continue;
    		ii x = dfs(u, v, !r);
     
    		//cerr << "VISITED " << u << " returned " << x.first << " " << x.second << endl;
     
    		cmin = min(cmin, x.first);
    		cmax = max(cmax, x.second);
    	}
     
    	if(cmin == 1002) {
    		rans[ft] = v;
    		ft++;
    		return ii(ft-1, ft-1);
    	}
    	else {
    		if(r) {
    			/*for(int i=ft; i > cmax+1; --i) {
    				swap(rans[i], rans[i-1]);
    			}*/
    			rans[cmax+1] = v;
    			ft++;
    		}
    		else {
    			for(int i=ft; i > cmin; --i) {
    				swap(rans[i], rans[i-1]);
    			}
    			rans[cmin] = v;
    			ft++;
    		}
    		return ii(cmin, max(cmax, ft-1));
    	}
     
     
    }
     
    std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    	
    	al = vvi(n, vi());
    	for(int i=0; i < n-1; ++i) {
    		al[u[i]].push_back(v[i]);
    		al[v[i]].push_back(u[i]);
    	}
     
    	rans = vi(1001, -1);
    	ft = 0;
     
    	dfs(0, -1, 0);
    	vi ans(n);
    	/*for(int i=0; i < 1001; ++i) {
    		if(rans[i] != -1) {
    			cerr << "rans[" << i << "] = " << rans[i] << endl;
    		}
    	}*/
    	for(int i=0; i < n; ++i) {
    		ans[rans[i]] = i;
    	}
    	return ans;
     
    }
     
    int find_next_station(int s, int t, std::vector<int> c) {
    	int m = c.size();
    	if(m == 1) return c[0];
    	bool ismax = true;
    	for(int i=0; i < m; ++i) {
    		if(s < c[i]) ismax = false;
    	}
    	if(s == 0) {
    		vi otc;
    		for(int i=0; i < m; ++i) {
    			 otc.push_back(c[i]);
    		}
    		sort(otc.begin(), otc.end());
    		for(int i=0; i < m; ++i) {
    			if(t <= otc[i]) return otc[i];
    		}
    	}
    	else if(ismax) {
    		int minv = 1002;
    		for(int i=0; i < m; ++i) minv = min(c[i], minv);
    		if(t <= minv || t >= s) return minv;
    		vi otc;
    		for(int i=0; i < m; ++i) {
    			if(c[i] != minv) otc.push_back(c[i]);
    		}
    		sort(otc.begin(), otc.end());
    		for(int i=m-2; i > -1; --i) {
    			if(t >= otc[i]) return otc[i];
    		}
    		return minv;
    	}
    	else {
    		int maxv = -1;
    		for(int i=0; i < m; ++i) maxv = max(c[i], maxv);
    		if(t >= maxv || t <= s) return maxv;
    		vi otc;
    		for(int i=0; i < m; ++i) {
    			if(c[i] != maxv) otc.push_back(c[i]);
    		}
    		sort(otc.begin(), otc.end());
    		for(int i=0; i < m-1; ++i) {
    			if(t <= otc[i]) return otc[i];
    		}
    		return maxv;
    	}
     
     
    }

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:130:5: warning: control reaches end of non-void function [-Wreturn-type]
  130 |     }
      |     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 1024 KB Output is correct
2 Correct 504 ms 1024 KB Output is correct
3 Correct 866 ms 880 KB Output is correct
4 Correct 675 ms 888 KB Output is correct
5 Correct 577 ms 792 KB Output is correct
6 Correct 509 ms 1024 KB Output is correct
7 Correct 449 ms 768 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 5 ms 896 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 435 ms 1024 KB Output is correct
2 Correct 554 ms 828 KB Output is correct
3 Correct 924 ms 760 KB Output is correct
4 Correct 734 ms 892 KB Output is correct
5 Correct 692 ms 892 KB Output is correct
6 Correct 440 ms 784 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 1024 KB Output is correct
2 Correct 540 ms 1024 KB Output is correct
3 Correct 985 ms 888 KB Output is correct
4 Correct 801 ms 888 KB Output is correct
5 Correct 566 ms 760 KB Output is correct
6 Correct 476 ms 1024 KB Output is correct
7 Correct 471 ms 1016 KB Output is correct
8 Correct 3 ms 900 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 590 ms 768 KB Output is correct
12 Correct 449 ms 1024 KB Output is correct
13 Correct 519 ms 1024 KB Output is correct
14 Correct 452 ms 828 KB Output is correct
15 Correct 55 ms 888 KB Output is correct
16 Correct 68 ms 828 KB Output is correct
17 Correct 107 ms 908 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 792 KB Output is correct
2 Correct 684 ms 792 KB Output is correct
3 Correct 592 ms 784 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 579 ms 768 KB Output is correct
8 Correct 871 ms 884 KB Output is correct
9 Correct 651 ms 768 KB Output is correct
10 Correct 622 ms 888 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 6 ms 1024 KB Output is correct
13 Correct 4 ms 896 KB Output is correct
14 Correct 4 ms 892 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 490 ms 768 KB Output is correct
17 Correct 505 ms 888 KB Output is correct
18 Correct 486 ms 1024 KB Output is correct
19 Correct 515 ms 892 KB Output is correct
20 Correct 514 ms 888 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 1024 KB Output is correct
2 Correct 474 ms 1016 KB Output is correct
3 Correct 860 ms 768 KB Output is correct
4 Correct 702 ms 768 KB Output is correct
5 Correct 580 ms 760 KB Output is correct
6 Correct 479 ms 1008 KB Output is correct
7 Correct 454 ms 768 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 486 ms 1032 KB Output is correct
12 Correct 524 ms 816 KB Output is correct
13 Correct 817 ms 792 KB Output is correct
14 Correct 670 ms 896 KB Output is correct
15 Correct 606 ms 892 KB Output is correct
16 Correct 459 ms 820 KB Output is correct
17 Correct 617 ms 768 KB Output is correct
18 Correct 456 ms 1024 KB Output is correct
19 Correct 457 ms 1196 KB Output is correct
20 Correct 456 ms 824 KB Output is correct
21 Correct 63 ms 768 KB Output is correct
22 Correct 73 ms 840 KB Output is correct
23 Correct 110 ms 772 KB Output is correct
24 Correct 5 ms 640 KB Output is correct
25 Correct 5 ms 768 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 4 ms 640 KB Output is correct
28 Correct 2 ms 660 KB Output is correct
29 Correct 489 ms 768 KB Output is correct
30 Correct 553 ms 892 KB Output is correct
31 Correct 489 ms 896 KB Output is correct
32 Correct 525 ms 892 KB Output is correct
33 Correct 487 ms 892 KB Output is correct
34 Correct 348 ms 1024 KB Output is correct
35 Correct 462 ms 1024 KB Output is correct
36 Correct 476 ms 1024 KB Output is correct
37 Correct 447 ms 1132 KB Output is correct
38 Correct 487 ms 1024 KB Output is correct
39 Correct 466 ms 1008 KB Output is correct
40 Correct 449 ms 1024 KB Output is correct
41 Correct 457 ms 1136 KB Output is correct
42 Correct 60 ms 812 KB Output is correct
43 Correct 108 ms 792 KB Output is correct
44 Correct 126 ms 792 KB Output is correct
45 Correct 169 ms 768 KB Output is correct
46 Correct 310 ms 1024 KB Output is correct
47 Correct 306 ms 1024 KB Output is correct
48 Correct 61 ms 780 KB Output is correct
49 Correct 66 ms 768 KB Output is correct