oj.uz

Submission #1024416

# Submission time Handle Problem Language Result Execution time Memory
1024416 2024-07-16T04:11:18 Z Ahmed_Solyman Stations (IOI20_stations) C++14
100 / 100
 638 ms 1272 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
vector<vector<int>>adj;
vector<int>l,r,p,ret;
int mark=0;
void dfs(int node,int par,int dep){
    if(dep)ret[node]=mark++;
    for(auto i:adj[node])
        if(i!=par)dfs(i,node,1-dep);
    if(!dep)ret[node]=mark++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
    mark=0;
    l=r=p=ret=vector<int>(n);
    adj=vector<vector<int>>(n);
    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,1);
    return ret;
}
int find_next_station(int s, int t,vector<int> c){
    int m=(int)c.size();
  	for(int i=0;i<m;i++){
      	if(c[i]==t)return t;
    }
    if(s==0){
        for(int i=m-1;i>=0;i--){
            int in=(i==0?s+1:c[i-1]+1);
            int out=c[i];
            if(t>=in && t<=out){
                return c[i];
            }
        }
        assert(0);
    }
    if(s<c[0]){///given is the in[s]
        int p=c[m-1];
        for(int i=m-2;i>=0;i--){
            int in=(i==0?s+1:c[i-1]+1);
            int out=c[i];
            if(t>=in && t<=out){
                return c[i];
            }
        }
        return p;
    }
    else{///given is the out[s]
        int p=c[0];
        for(int i=1;i<m;i++){
            int in=c[i];
            int out=(i==m-1?s-1:c[i+1]-1);
            if(t>=in && t<=out){
                return c[i];
            }
        }
        return p;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 940 KB Output is correct
2 Correct 284 ms 940 KB Output is correct
3 Correct 597 ms 688 KB Output is correct
4 Correct 481 ms 684 KB Output is correct
5 Correct 389 ms 684 KB Output is correct
6 Correct 302 ms 940 KB Output is correct
7 Correct 306 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 684 KB Output is correct
2 Correct 343 ms 684 KB Output is correct
3 Correct 620 ms 684 KB Output is correct
4 Correct 448 ms 684 KB Output is correct
5 Correct 401 ms 684 KB Output is correct
6 Correct 327 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 940 KB Output is correct
2 Correct 330 ms 940 KB Output is correct
3 Correct 578 ms 684 KB Output is correct
4 Correct 431 ms 684 KB Output is correct
5 Correct 403 ms 708 KB Output is correct
6 Correct 312 ms 1192 KB Output is correct
7 Correct 274 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 387 ms 684 KB Output is correct
12 Correct 310 ms 1020 KB Output is correct
13 Correct 285 ms 940 KB Output is correct
14 Correct 331 ms 684 KB Output is correct
15 Correct 28 ms 768 KB Output is correct
16 Correct 45 ms 776 KB Output is correct
17 Correct 75 ms 764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 684 KB Output is correct
2 Correct 470 ms 684 KB Output is correct
3 Correct 449 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 764 KB Output is correct
7 Correct 435 ms 684 KB Output is correct
8 Correct 590 ms 684 KB Output is correct
9 Correct 483 ms 936 KB Output is correct
10 Correct 437 ms 684 KB Output is correct
11 Correct 3 ms 776 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 772 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 368 ms 684 KB Output is correct
17 Correct 328 ms 680 KB Output is correct
18 Correct 321 ms 684 KB Output is correct
19 Correct 372 ms 684 KB Output is correct
20 Correct 329 ms 712 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 940 KB Output is correct
2 Correct 310 ms 940 KB Output is correct
3 Correct 614 ms 684 KB Output is correct
4 Correct 460 ms 684 KB Output is correct
5 Correct 421 ms 684 KB Output is correct
6 Correct 285 ms 944 KB Output is correct
7 Correct 304 ms 684 KB Output is correct
8 Correct 2 ms 1028 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 0 ms 764 KB Output is correct
11 Correct 331 ms 768 KB Output is correct
12 Correct 354 ms 684 KB Output is correct
13 Correct 638 ms 684 KB Output is correct
14 Correct 465 ms 684 KB Output is correct
15 Correct 380 ms 712 KB Output is correct
16 Correct 303 ms 684 KB Output is correct
17 Correct 385 ms 684 KB Output is correct
18 Correct 322 ms 1196 KB Output is correct
19 Correct 306 ms 1020 KB Output is correct
20 Correct 306 ms 684 KB Output is correct
21 Correct 33 ms 776 KB Output is correct
22 Correct 53 ms 700 KB Output is correct
23 Correct 76 ms 776 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 3 ms 776 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 0 ms 780 KB Output is correct
29 Correct 335 ms 684 KB Output is correct
30 Correct 345 ms 684 KB Output is correct
31 Correct 354 ms 940 KB Output is correct
32 Correct 393 ms 684 KB Output is correct
33 Correct 356 ms 684 KB Output is correct
34 Correct 241 ms 956 KB Output is correct
35 Correct 330 ms 1020 KB Output is correct
36 Correct 335 ms 1272 KB Output is correct
37 Correct 334 ms 940 KB Output is correct
38 Correct 293 ms 940 KB Output is correct
39 Correct 342 ms 1188 KB Output is correct
40 Correct 280 ms 1060 KB Output is correct
41 Correct 357 ms 940 KB Output is correct
42 Correct 30 ms 748 KB Output is correct
43 Correct 56 ms 684 KB Output is correct
44 Correct 81 ms 756 KB Output is correct
45 Correct 94 ms 716 KB Output is correct
46 Correct 202 ms 684 KB Output is correct
47 Correct 194 ms 684 KB Output is correct
48 Correct 28 ms 772 KB Output is correct
49 Correct 35 ms 836 KB Output is correct