oj.uz

Submission #1022444

# Submission time Handle Problem Language Result Execution time Memory
1022444 2024-07-13T14:04:33 Z edogawa_something Fountain Parks (IOI21_parks) C++17
5 / 100
 89 ms 63680 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first 
#define S second 
#define all(v) v.begin(),v.end()
const ll M=2e6+50;
vii adj[M];
bool vis[M];
void dfs(ll x){
    if(vis[x])
    return;
    vis[x]=1;
    for(auto it:adj[x]){
        dfs(it);
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<pair<int,int>>f,m,b;
    for(int i=0;i<x.size();i++){
        if(x[i]==2){
            f.pb({y[i],i});
        }
        else
        b.pb({y[i],i});
    }
    sort(all(f)),sort(all(b));
    vector<int>e1,e2,ax,ay;
    for(int i=0;i<ll(f.size())-1;i++){
        if(f[i+1].F-f[i].F==2){
        e1.pb(f[i].S);
        e2.pb(f[i+1].S);
        ax.pb(1);
        ay.pb(f[i].F+1);
        }
    }
    for(int i=0;i<ll(b.size())-1;i++){
        if(b[i+1].F-b[i].F==2){
        e1.pb(b[i].S);
        e2.pb(b[i+1].S);
        ax.pb(5);
        ay.pb(b[i].F+1);
        }
    }
    ll i=0,j=0;
    while(1){
        if(i==f.size()||j==b.size())
        break;
        if(f[i].F==b[j].F){
            e1.pb(f[i].S),e2.pb(b[j].S);
            ax.pb(3),ay.pb(f[i].S-1);
            i++,j++;
        }
        else if(f[i].F<b[j].F){
            i++;
        }
        else if(b[j].F<f[i].F){
            j++;
        }
    }
    for(int i=0;i<e1.size();i++)
    adj[e1[i]].pb(e2[i]),adj[e2[i]].pb(e1[i]);
    dfs(0);
    for(int i=0;i<x.size();i++){
        if(!vis[i])
        return 0;
    }
    build(e1,e2,ax,ay);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:51:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(i==f.size()||j==b.size())
      |            ~^~~~~~~~~~
parks.cpp:51:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(i==f.size()||j==b.size())
      |                         ~^~~~~~~~~~
parks.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<e1.size();i++)
      |                 ~^~~~~~~~~~
parks.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct
17 Incorrect 22 ms 47196 KB b[2] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct
17 Incorrect 22 ms 47196 KB b[2] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct
17 Incorrect 24 ms 47216 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct
17 Incorrect 89 ms 63680 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 29 ms 47196 KB Output is correct
3 Correct 23 ms 47192 KB Output is correct
4 Correct 21 ms 47192 KB Output is correct
5 Correct 22 ms 47196 KB Output is correct
6 Correct 23 ms 47192 KB Output is correct
7 Correct 22 ms 47196 KB Output is correct
8 Correct 22 ms 47196 KB Output is correct
9 Correct 82 ms 61068 KB Output is correct
10 Correct 28 ms 48728 KB Output is correct
11 Correct 43 ms 54660 KB Output is correct
12 Correct 27 ms 49380 KB Output is correct
13 Correct 32 ms 51656 KB Output is correct
14 Correct 25 ms 47452 KB Output is correct
15 Correct 23 ms 47452 KB Output is correct
16 Correct 81 ms 60068 KB Output is correct
17 Incorrect 22 ms 47196 KB b[2] = 2 is not an odd integer
18 Halted 0 ms 0 KB -