oj.uz

Submission #557008

# Submission time Handle Problem Language Result Execution time Memory
557008 2022-05-04T14:33:57 Z fcmalkcin Stations (IOI20_stations) C++17
100 / 100
 832 ms 5552 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+50;
const ll mod=1e9+7  ;
const ll base=1e9;


/// top 6 VietNam in APIO please god i am so fucking depressed
/// goal 6/7

#include "stations.h"

ll res[maxn];
ll cnt=0;
vector<ll> adj[maxn];

void dfs(ll u,ll par,ll t)
{
   if (t%2) cnt++,res[u]=cnt;
   for (auto to:adj[u])
   {
       if (to==par) continue;
       dfs(to,u,t+1);
   }
   if ((t%2)==0) cnt++,res[u]=cnt;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i=1;i<=n-1;i++)
    {
        ll x=u[i-1];
        ll y=v[i-1];
        x++;
        y++;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    cnt=0;
    dfs(1,0,0);
    vector<ll> ans;
    for (int i=1;i<=n;i++) ans.pb(res[i]-1),adj[i].clear();
    return ans;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s<c[0])
    {
        sort(c.begin(),c.end());
        for (int i=0;i+1<c.size();i++)
        {
            if (t>=s&&t<=c[i]) return c[i];
        }
        return c.back();
    }
    else
    {
        sort(c.begin(),c.end());
        c.pb(s);
        for (int i=1;i+1<c.size();i++)
        {
            if (t>=c[i]&&t<c[i+1]) return c[i];
        }
        return c[0];
    }
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("CONVEXHULL.inp", "r"))
    {
        freopen("CONVEXHULL.inp", "r", stdin);
        freopen("CONVEXHULL.out", "w", stdout);
    }

}*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:57:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i=0;i+1<c.size();i++)
      |                      ~~~^~~~~~~~~
stations.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int i=1;i+1<c.size();i++)
      |                      ~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 5412 KB Output is correct
2 Correct 403 ms 5424 KB Output is correct
3 Correct 818 ms 5304 KB Output is correct
4 Correct 598 ms 5296 KB Output is correct
5 Correct 506 ms 5400 KB Output is correct
6 Correct 419 ms 5404 KB Output is correct
7 Correct 423 ms 5408 KB Output is correct
8 Correct 5 ms 5372 KB Output is correct
9 Correct 6 ms 5364 KB Output is correct
10 Correct 4 ms 5372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 5280 KB Output is correct
2 Correct 479 ms 5292 KB Output is correct
3 Correct 796 ms 5280 KB Output is correct
4 Correct 583 ms 5280 KB Output is correct
5 Correct 514 ms 5300 KB Output is correct
6 Correct 397 ms 5288 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 5428 KB Output is correct
2 Correct 423 ms 5412 KB Output is correct
3 Correct 782 ms 5280 KB Output is correct
4 Correct 540 ms 5284 KB Output is correct
5 Correct 550 ms 5292 KB Output is correct
6 Correct 383 ms 5428 KB Output is correct
7 Correct 412 ms 5408 KB Output is correct
8 Correct 5 ms 5364 KB Output is correct
9 Correct 6 ms 5360 KB Output is correct
10 Correct 4 ms 5364 KB Output is correct
11 Correct 489 ms 5296 KB Output is correct
12 Correct 407 ms 5552 KB Output is correct
13 Correct 441 ms 5412 KB Output is correct
14 Correct 368 ms 5284 KB Output is correct
15 Correct 51 ms 5364 KB Output is correct
16 Correct 65 ms 5320 KB Output is correct
17 Correct 105 ms 5280 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 5280 KB Output is correct
2 Correct 561 ms 5284 KB Output is correct
3 Correct 534 ms 5404 KB Output is correct
4 Correct 5 ms 5364 KB Output is correct
5 Correct 5 ms 5364 KB Output is correct
6 Correct 2 ms 5368 KB Output is correct
7 Correct 537 ms 5284 KB Output is correct
8 Correct 789 ms 5296 KB Output is correct
9 Correct 552 ms 5284 KB Output is correct
10 Correct 517 ms 5284 KB Output is correct
11 Correct 6 ms 5364 KB Output is correct
12 Correct 6 ms 5364 KB Output is correct
13 Correct 5 ms 5364 KB Output is correct
14 Correct 6 ms 5372 KB Output is correct
15 Correct 3 ms 5364 KB Output is correct
16 Correct 458 ms 5300 KB Output is correct
17 Correct 391 ms 5280 KB Output is correct
18 Correct 412 ms 5280 KB Output is correct
19 Correct 404 ms 5296 KB Output is correct
20 Correct 379 ms 5280 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 5412 KB Output is correct
2 Correct 407 ms 5408 KB Output is correct
3 Correct 832 ms 5280 KB Output is correct
4 Correct 560 ms 5284 KB Output is correct
5 Correct 529 ms 5284 KB Output is correct
6 Correct 419 ms 5412 KB Output is correct
7 Correct 402 ms 5192 KB Output is correct
8 Correct 5 ms 5364 KB Output is correct
9 Correct 5 ms 5364 KB Output is correct
10 Correct 3 ms 5364 KB Output is correct
11 Correct 373 ms 5296 KB Output is correct
12 Correct 481 ms 5296 KB Output is correct
13 Correct 738 ms 5284 KB Output is correct
14 Correct 569 ms 5280 KB Output is correct
15 Correct 494 ms 5292 KB Output is correct
16 Correct 404 ms 5280 KB Output is correct
17 Correct 523 ms 5280 KB Output is correct
18 Correct 425 ms 5288 KB Output is correct
19 Correct 389 ms 5428 KB Output is correct
20 Correct 342 ms 5284 KB Output is correct
21 Correct 54 ms 5364 KB Output is correct
22 Correct 62 ms 5280 KB Output is correct
23 Correct 98 ms 5280 KB Output is correct
24 Correct 8 ms 5352 KB Output is correct
25 Correct 7 ms 5364 KB Output is correct
26 Correct 7 ms 5364 KB Output is correct
27 Correct 5 ms 5376 KB Output is correct
28 Correct 4 ms 5372 KB Output is correct
29 Correct 456 ms 5296 KB Output is correct
30 Correct 386 ms 5280 KB Output is correct
31 Correct 433 ms 5300 KB Output is correct
32 Correct 495 ms 5296 KB Output is correct
33 Correct 506 ms 5280 KB Output is correct
34 Correct 306 ms 5412 KB Output is correct
35 Correct 397 ms 5424 KB Output is correct
36 Correct 401 ms 5408 KB Output is correct
37 Correct 447 ms 5304 KB Output is correct
38 Correct 363 ms 5292 KB Output is correct
39 Correct 459 ms 5464 KB Output is correct
40 Correct 436 ms 5308 KB Output is correct
41 Correct 417 ms 5292 KB Output is correct
42 Correct 66 ms 5280 KB Output is correct
43 Correct 109 ms 5280 KB Output is correct
44 Correct 136 ms 5384 KB Output is correct
45 Correct 180 ms 5296 KB Output is correct
46 Correct 311 ms 5300 KB Output is correct
47 Correct 299 ms 5296 KB Output is correct
48 Correct 73 ms 5420 KB Output is correct
49 Correct 45 ms 5360 KB Output is correct