Submission #960410

#	Time	Username	Problem	Language	Result	Execution time	Memory
960410		LucaIlie	IOI Fever (JOI21_fever)	C++17	6 / 100	1 ms	2396 KiB

fever

#include <bits/stdc++.h>

using namespace std;

struct house {
    int x, y;
};

const int MAX_N = 2e5;
const int INF = 5e8;
int dir[MAX_N], t[MAX_N];
house houses[MAX_N];
unordered_map<int, set<pair<int, int>>> diag1, diag2, vert, horiz;
vector<int> q;

void visitt( set<pair<int, int>> &s, int l, int r, int i, int d ) {
    vector<int> del;

    auto p = s.lower_bound( { l, 0 } );
    while ( p != s.end() && p->first <= r ) {
        int j = p->second;


        if ( dir[j] == d ) {
            del.push_back( j );
            q.push_back( j );
            if ( houses[i].x == houses[j].x )
                t[j] = abs( houses[j].y - houses[i].y ) / 2;
            else if ( houses[i].y == houses[j].y )
                t[j] = abs( houses[j].x - houses[j].x ) / 2;
            else
                t[j] = abs( houses[j].x - houses[i].x );
        }

        p++;
    }

    for ( int j: del ) {
        diag1[houses[j].x + houses[j].y].erase( { houses[j].x, j } );
        diag2[houses[j].x - houses[j].y].erase( { houses[j].x, j } );
        vert[houses[j].x].erase( { houses[j].y, j } );
        horiz[houses[j].y].erase( { houses[j].x, j } );
    }
}

int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> houses[i].x >> houses[i].y;
        if ( i != 0 ) {
            houses[i].x -= houses[0].x;
            houses[i].y -= houses[0].y;
        }
    }

    for ( int i = 1; i < n; i++ ) {
        if ( houses[i].x > 0 ) {
            if ( houses[i].y > 0 )
                dir[i] = (houses[i].x > houses[i].y ? 3 : 1);
            else
                dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
        } else {
            if ( houses[i].y > 0 )
                dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
            else
                dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
        }
    }

    int maxVisited = 0;
    for ( int d = 0; d < 4; d++ ) {
        diag1.clear();
        diag2.clear();
        for ( int i = 1; i < n; i++ ) {
            diag1[houses[i].x + houses[i].y].insert( { houses[i].x, i } );
            diag2[houses[i].x - houses[i].y].insert( { houses[i].x, i } );
            vert[houses[i].x].insert( { houses[i].y, i } );
            horiz[houses[i].y].insert( { houses[i].x, i } );
        }

        int visited = 0;
        q.clear();
        q.push_back( 0 );
        dir[0] = d;
        t[0] = 0;
        while ( visited < q.size() ) {
            int pos = visited + rand() % (q.size() - visited);
            int i = q[visited];
            visited++;

            //printf( "%d (%d %d) %d %d\n", i, houses[i].x, houses[i].y, t[i], dir[i] );\

            int x = houses[i].x, y = houses[i].y;
            if ( dir[i] == 0 ) {
                visitt( vert[x], y + t[i], INF, i, 1 );
                visitt( diag1[x + y], -INF, x - t[i], i, 2 );
                visitt( diag2[x - y], x + t[i], INF, i, 3 );
            } else if ( dir[i] == 1 ) {
                visitt( vert[x], -INF, y - t[i], i, 0 );
                visitt( diag1[x + y], x + t[i], INF, i, 3 );
                visitt( diag2[x - y], -INF, x - t[i], i, 2 );
            } else if ( dir[i] == 2 ) {
                visitt( horiz[y], x + t[i], INF, i, 3 );
                visitt( diag1[x + y], x + t[i], INF, i, 0 );
                visitt( diag2[x - y], x + t[i], INF, i, 1 );
            } else if ( dir[i] == 3 ) {
                visitt( horiz[y], -INF, x - t[i], i, 2 );
                visitt( diag1[x + y], -INF, x - t[i], i, 1 );
                visitt( diag2[x - y], -INF, x - t[i], i, 0 );
            }
        }

        //printf( "DIR %d: %d\n", d, visited );
        maxVisited = max( maxVisited, visited );
    }

    cout << maxVisited;

    return 0;
}
/*
 * d == 0 sus
 * d == 1 jos
 * d == 2 dreapta
 * d == 3 stanga
 */

Compilation message (stderr)

fever.cpp:93:13: warning: multi-line comment [-Wcomment]
   93 |             //printf( "%d (%d %d) %d %d\n", i, houses[i].x, houses[i].y, t[i], dir[i] );\
      |             ^
fever.cpp: In function 'int main()':
fever.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while ( visited < q.size() ) {
      |                 ~~~~~~~~^~~~~~~~~~
fever.cpp:89:17: warning: unused variable 'pos' [-Wunused-variable]
   89 |             int pos = visited + rand() % (q.size() - visited);
      |                 ^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31