Submission #802288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802288	2023-08-02T11:25:19 Z	lollipop	Stations (IOI20_stations)	C++17	100 / 100	891 ms	12208 KB

stations

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int NN = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;

//#include "stations.h"

vector < int > v[ NN ] ;
int hh[ NN ] , timer = 0 ;
pair < int , int > tt[ NN ] ;
void dfs( int node , int parent , int h ){
     hh[ node ] = h ;
     tt[ node ].f = timer ; timer ++ ;
     for( auto x : v[ node ] ){
        if( x == parent ) continue ;
        dfs( x , node , h + 1 ) ; 
     }
     tt[ node ].s = timer ; timer ++ ;
}
vector<int> label(int n, int k, vector<int> U, vector<int> V){
  FOR( i , n ) v[ i ].clear() ;
     FOR( i , n - 1 ){
        v[ U[ i ] ].pb( V[ i ] ) ;
        v[ V[ i ] ].pb( U[ i ] ) ;
     }
     dfs( 0 , -1 , 0 ) ;
     set < pair < int , int > > se ;
     FOR( i , n ){
       se.insert( { tt[ i ].f , 0 } ) ;
       se.insert( { tt[ i ].s , 1 } ) ;
     }
     int cnt = 0 ;
     int mx = -1 , cur = 0 ;
     set < int > se1 , se2 ;
     FOR( i , 10 * n ){
      se1.insert( cur ) ; 
      se2.insert( cur + 1 ) ; cur += 2 ; 
     }
     for( auto x : se ){
       int nd ;
       if( x.s == 0 ){
         nd = *se1.upper_bound( mx ) ;
         mx = nd ;
       }
       else{
         nd = *se2.upper_bound( mx ) ;
         mx = nd ;
       }
       ma[ x.f ] = nd ; 
     }
     vector < int > rt ; 
     set < int > sis ;
     FOR( i , n ){
      if( hh[ i ] % 2 == 0 ){
         rt.pb( tt[ i ].f ) ;
         sis.insert( tt[ i ].f ) ;
      }
      else{
        sis.insert( tt[ i ].s ) ;
        rt.pb( tt[ i ].s ) ;
      }
     }
     int cccc = 0 ;
     for( auto x : sis ){
         ma[ x ] = cccc ; cccc ++ ;
     }
     FOR( i , n ) rt[ i ] = ma[ rt[ i ] ] ;
     return rt ;
}

int find_next_station(int s, int t, vector<int> c){
    if( c.size() == 1 ) return c[ 0 ] ;
    int ss = c.size() ;
    if( s < c[ 0 ] ){
        // anu gaqvs in-i
   //   if( t % 2 == 0 ){
         if( t < s ) return c[ ss - 1 ] ;
         if( t > c[ ss - 2 ] ) return c[ ss - 1 ] ;
         for( auto x : c ) if( x >= t ) return x ;
     // }
      // else{
      //   if( t < s ) return c[ ss - 1 ] ;
      //   if( t > c[ ss - 2 ] ) return c[ ss - 1 ] ; 
      //   for( auto x : c ) if( x >= t ) return x ;
      // }
    }
    else{
     // if( t % 2 == 0 ){
         if( t > s ) return c[ 0 ] ;
         if( t < c[ 1 ] ) return c[ 0 ] ;
         FOR( i , ss ){
          if( c[ i ] > t ) return c[ i - 1 ] ;
         }
         return c[ ss - 1 ] ;
    //  }
      // else{
      //    if( t > s ) return c[ 0 ] ;
      //    if( t < c[ 0 ] ) return c[ 0 ] ;
      //    FOR( i , ss ){
      //     if( c[ i ] > t ) return c[ i - 1 ] ;
      //    }
      //    return c[ ss - 1 ] ;
      // }     
    }

}




// 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 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:59:10: warning: unused variable 'cnt' [-Wunused-variable]
   59 |      int cnt = 0 ;
      |          ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
  133 | }
      | ^

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	392 ms	11556 KB	Output is correct
2	Correct	322 ms	11992 KB	Output is correct
3	Correct	777 ms	10076 KB	Output is correct
4	Correct	646 ms	9888 KB	Output is correct
5	Correct	479 ms	9892 KB	Output is correct
6	Correct	463 ms	11984 KB	Output is correct
7	Correct	330 ms	11232 KB	Output is correct
8	Correct	4 ms	9988 KB	Output is correct
9	Correct	5 ms	9988 KB	Output is correct
10	Correct	4 ms	9976 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	384 ms	11924 KB	Output is correct
2	Correct	432 ms	11172 KB	Output is correct
3	Correct	799 ms	9944 KB	Output is correct
4	Correct	501 ms	9888 KB	Output is correct
5	Correct	515 ms	9976 KB	Output is correct
6	Correct	397 ms	11108 KB	Output is correct

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	505 ms	11500 KB	Output is correct
2	Correct	339 ms	12048 KB	Output is correct
3	Correct	790 ms	9948 KB	Output is correct
4	Correct	548 ms	9948 KB	Output is correct
5	Correct	440 ms	9892 KB	Output is correct
6	Correct	444 ms	12056 KB	Output is correct
7	Correct	426 ms	11232 KB	Output is correct
8	Correct	6 ms	10008 KB	Output is correct
9	Correct	8 ms	9984 KB	Output is correct
10	Correct	5 ms	9980 KB	Output is correct
11	Correct	597 ms	9892 KB	Output is correct
12	Correct	364 ms	11956 KB	Output is correct
13	Correct	439 ms	12208 KB	Output is correct
14	Correct	297 ms	11172 KB	Output is correct
15	Correct	45 ms	10176 KB	Output is correct
16	Correct	59 ms	11100 KB	Output is correct
17	Correct	126 ms	12028 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	664 ms	9948 KB	Output is correct
2	Correct	497 ms	9892 KB	Output is correct
3	Correct	421 ms	9964 KB	Output is correct
4	Correct	5 ms	9988 KB	Output is correct
5	Correct	8 ms	9988 KB	Output is correct
6	Correct	5 ms	9988 KB	Output is correct
7	Correct	435 ms	9948 KB	Output is correct
8	Correct	891 ms	9892 KB	Output is correct
9	Correct	636 ms	9892 KB	Output is correct
10	Correct	524 ms	9892 KB	Output is correct
11	Correct	9 ms	9980 KB	Output is correct
12	Correct	8 ms	9980 KB	Output is correct
13	Correct	7 ms	10052 KB	Output is correct
14	Correct	6 ms	9988 KB	Output is correct
15	Correct	4 ms	9988 KB	Output is correct
16	Correct	436 ms	9888 KB	Output is correct
17	Correct	415 ms	9892 KB	Output is correct
18	Correct	447 ms	9892 KB	Output is correct
19	Correct	416 ms	9976 KB	Output is correct
20	Correct	353 ms	9956 KB	Output is correct

Subtask #5

61.0 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	414 ms	11624 KB	Output is correct
2	Correct	440 ms	11980 KB	Output is correct
3	Correct	659 ms	9940 KB	Output is correct
4	Correct	643 ms	9948 KB	Output is correct
5	Correct	506 ms	9892 KB	Output is correct
6	Correct	482 ms	11988 KB	Output is correct
7	Correct	305 ms	11116 KB	Output is correct
8	Correct	5 ms	9980 KB	Output is correct
9	Correct	6 ms	9980 KB	Output is correct
10	Correct	4 ms	9980 KB	Output is correct
11	Correct	406 ms	11920 KB	Output is correct
12	Correct	445 ms	11220 KB	Output is correct
13	Correct	826 ms	9908 KB	Output is correct
14	Correct	554 ms	10016 KB	Output is correct
15	Correct	537 ms	10096 KB	Output is correct
16	Correct	397 ms	11124 KB	Output is correct
17	Correct	491 ms	9892 KB	Output is correct
18	Correct	376 ms	11980 KB	Output is correct
19	Correct	429 ms	12112 KB	Output is correct
20	Correct	400 ms	11228 KB	Output is correct
21	Correct	57 ms	10080 KB	Output is correct
22	Correct	76 ms	11060 KB	Output is correct
23	Correct	120 ms	11944 KB	Output is correct
24	Correct	7 ms	10064 KB	Output is correct
25	Correct	7 ms	9944 KB	Output is correct
26	Correct	8 ms	9960 KB	Output is correct
27	Correct	7 ms	9980 KB	Output is correct
28	Correct	4 ms	9980 KB	Output is correct
29	Correct	371 ms	9948 KB	Output is correct
30	Correct	325 ms	9952 KB	Output is correct
31	Correct	431 ms	9944 KB	Output is correct
32	Correct	425 ms	9892 KB	Output is correct
33	Correct	534 ms	9968 KB	Output is correct
34	Correct	264 ms	11956 KB	Output is correct
35	Correct	364 ms	12096 KB	Output is correct
36	Correct	332 ms	12040 KB	Output is correct
37	Correct	399 ms	11976 KB	Output is correct
38	Correct	422 ms	12044 KB	Output is correct
39	Correct	318 ms	12068 KB	Output is correct
40	Correct	443 ms	12084 KB	Output is correct
41	Correct	401 ms	12084 KB	Output is correct
42	Correct	80 ms	11432 KB	Output is correct
43	Correct	131 ms	12140 KB	Output is correct
44	Correct	114 ms	11844 KB	Output is correct
45	Correct	171 ms	11988 KB	Output is correct
46	Correct	275 ms	11476 KB	Output is correct
47	Correct	290 ms	11988 KB	Output is correct
48	Correct	83 ms	11780 KB	Output is correct
49	Correct	76 ms	12068 KB	Output is correct