oj.uz

Submission #417555

# Submission time Handle Problem Language Result Execution time Memory
417555 2021-06-03T23:50:35 Z humbertoyusta IOI Fever (JOI21_fever) C++14
6 / 100
 5 ms 5020 KB 
    /**   Created by: Humberto Yusta
          Codeforces User: humbertoyusta
          Country: Cuba                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline","03") // Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero=upper") // Enable AVX
//#pragma GCC target("avx2") // Enable AVX
//#pragma comment(linker, "/STACK:1024000000,1024000000") // Increase stack limit
//#pragma GCC target("sse,sse2,sse,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // I don't know what it is
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 200010;
const int mod = 1000000007;
const int mod2 = 998244353;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 1ll * mod * mod;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return pwur * pwur % mod;
}
int modinv(int x){ return qpow(x,mod-2); }
bool isprime(int x){
    for(int i=2; i*i<=x; i++)
        if( x % i == 0 )
            return false;
    return true;
}
/// My Code -------------------------------------------------

int n, res;
map<int,set<ii>> mp, imp;
vector<pair<int,ii>> g[maxn];
priority_queue<pair<ii,ii>> q;

void bfs(){
    while( !q.empty() ){

        ii nod = q.top().f;
        int dir = q.top().s.f;
        int lwbound = q.top().s.s;
        q.pop();

        if( dir == 4 || dir == 3 || dir == 2 || dir == 1 ){
            while( !mp[nod.f+nod.s].empty() ){
                ii nwn = *prev(mp[nod.f+nod.s].end());
                //db(nwn.f - nod.f)
                if( nwn.f - nod.f < lwbound ) break;

                q.push({nwn,{dir%4+1,nwn.f - nod.f}});//db("4")db(nwn.f)db(nwn.s)
                mp[nwn.f+nwn.s].erase(nwn);
                imp[nwn.f-nwn.s].erase(nwn);
            }
        }

        if( dir == 4 || dir == 3 || dir == 2 || dir == 1 ){
            while( !imp[nod.f-nod.s].empty() ){
                ii nwn = *imp[nod.f-nod.s].begin();
                //db(nod.f - nwn.f)
                if( nod.f - nwn.f < lwbound ) break;

                q.push({nwn,{dir%4+1,nod.f - nwn.f}});//db("3")db(nwn.f)db(nwn.s)
                mp[nwn.f+nwn.s].erase(nwn);
                imp[nwn.f-nwn.s].erase(nwn);
            }
        }

        if( dir == 4 || dir == 3 || dir == 2 || dir == 1 ){
            while( !mp[nod.f+nod.s].empty() ){
                ii nwn = *mp[nod.f+nod.s].begin();
                //db(nod.f - nwn.f)
                if( nod.f - nwn.f < lwbound ) break;

                q.push({nwn,{dir%4+1,nod.f - nwn.f}});//db("2")db(nwn.f)db(nwn.s)
                mp[nwn.f+nwn.s].erase(nwn);
                imp[nwn.f-nwn.s].erase(nwn);
            }
        }

        if( dir == 4 || dir == 3 || dir == 2 || dir == 1 ){
            while( !imp[nod.f-nod.s].empty() ){
                ii nwn = *prev(imp[nod.f-nod.s].end());
                //db(nwn.f - nod.f)
                if( nwn.f - nod.f < lwbound ) break;

                q.push({nwn,{dir%4+1,nwn.f - nod.f}});//db("1")db(nwn.f)db(nwn.s)
                mp[nwn.f+nwn.s].erase(nwn);
                imp[nwn.f-nwn.s].erase(nwn);
            }
        }

        res ++;

    }
}

int solve(vector<ii> &vx,int init_dir){

    mp.clear();
    imp.clear();

    int cnt = 0;
    for(auto i : vx){
        int u = i.f;
        int v = i.s;
        cnt ++;
        mp[u+v].insert({u,v});
        imp[u-v].insert({u,v});
    }

    res = 0;

    mp[vx[0].f+vx[0].s].erase({vx[0].f,vx[0].s});
    imp[vx[0].f-vx[0].s].erase({vx[0].f,vx[0].s});
    while( !q.empty() ) q.pop();

    q.push({ { vx[0].f , vx[0].s } , { init_dir , 0 } });
    bfs();
    //db(res)
    return res;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(10);
    srand(time(NULL));

    //freopen("sample-05-in.txt","r",stdin);
    //freopen("a.in","w",stdout);

    cin >> n;

    vector<ii> vx;

    for(int i=1; i<=n; i++){
        int u, v;
        cin >> u >> v;
        vx.pb({u,v});
    }

    int ans = 0;
    for(int i=1; i<=4; i++){
        ans = max( ans , solve( vx , i ) );
    }
    cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 4 ms 5020 KB Output is correct
4 Correct 5 ms 5012 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 5012 KB Output is correct
7 Correct 5 ms 5012 KB Output is correct
8 Correct 4 ms 5004 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 4 ms 5012 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 4 ms 5008 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 5 ms 4940 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5016 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 4 ms 5012 KB Output is correct
20 Correct 4 ms 4940 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 4 ms 4940 KB Output is correct
24 Correct 3 ms 4940 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 4 ms 5016 KB Output is correct
27 Correct 4 ms 4940 KB Output is correct
28 Correct 4 ms 4940 KB Output is correct
29 Correct 4 ms 5008 KB Output is correct
30 Correct 4 ms 4940 KB Output is correct
31 Correct 5 ms 5012 KB Output is correct
32 Incorrect 4 ms 4940 KB Output isn't correct