oj.uz

Submission #568735

# Submission time Handle Problem Language Result Execution time Memory
568735 2022-05-26T06:45:39 Z kwongweng IOI Fever (JOI21_fever) C++17
11 / 100
 4 ms 324 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
ll MOD1 = 998244353;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

ld pi = 3.141592653589793238;
struct segtree{
	vector<ll> op, ans;
	int sz = 0;
	void init(int n){
		sz = n;
		op.assign(4*n, -1);
		ans.assign(4*n, 0);
	}
	void prop(int v, int tl, int tr){
		if (op[v] == -1 || tl == tr) return;
		int tm = (tl+tr)/2;
		op[2*v] = op[v];
		op[2*v+1] = op[v];
		ll len1 = tm-tl+1, len2 = tr-tm;
		ans[2*v] = op[v] * len1;
		ans[2*v+1] = op[v] * len2;
		op[v] = -1;
	}
	void update(int v, int tl, int tr, int l, int r, int val){
		prop(v, tl, tr);
		if (l > r) return;
		if (tl == l && tr == r){
			op[v] = val;
			ll len = tr-tl+1;
			ans[v] = val * len;
			return;
		}
		int tm = (tl+tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
		ans[v] = ans[2*v] + ans[2*v+1];
	}
	void update(int l, int r, int val){
		update(1, 0, sz-1, l, r, val);
	}
	ll get(int v, int tl, int tr, int l, int r){
		prop(v, tl, tr);
		if (l > r) return 0;
		if (tl == l && tr == r) return ans[v];
		int tm = (tl+tr)/2;
		ll m1 = get(2*v, tl, tm, l, min(r, tm));
		ll m2 = get(2*v+1, tm+1, tr, max(l, tm+1), r);
		return m1 + m2;
	}
	ll get(int l, int r){
		return get(1, 0, sz-1, l, r);
	}
};

const int N = 100000;

vi dx = {0,0,-1,1};
vi dy = {1,-1,0,0};

void solve(){
    int n; cin >> n;
    vi x(n), y(n);
    FOR(i,0,n) cin >> x[i] >> y[i];
    int mx = 0;
    FOR(d1,0,4){
        vi used(n);
        vector<ll> t(n,MOD); // time getting infected 
        vi d(n);
        set<ii> st;
        t[0] = 0;
        //time getting infected, direction, start_point
        st.insert({0,0});
        used[0]=1;
        while (!st.empty()){
            ii cur = *st.begin();
            st.erase(st.begin());
            int u = cur.se;
            used[u]=1;
            FOR(j,0,n){
                if (used[j]) continue;
                FOR(d2,0,4){
                    if (d[u]==d2){
                        continue;
                    }
                    if (dx[d[u]] == dx[d2]){
                        continue;
                    }
                    if (dy[d[u]] == dy[d2]){
                        continue;
                    }
                    // x[u]+dx[d[u]]*k == x[j]+dx[d2]*k
                    ll X = (x[u]-x[j])/(dx[d2]-dx[d[u]]);
                    ll Y = (y[u]-y[j])/(dy[d2]-dy[d[u]]);
                    if (X==Y && abs(X)>=t[u]){
                        X = abs(X);
                        if (t[j] > X){
                            if (t[j] != MOD) st.erase({t[j],j});
                            t[j] = X;
                            d[j] = d2;
                            st.insert({t[j],j});
                        }
                    }
                }
            }
        }
        int cnt = 0;
        FOR(i,0,n) cnt+=used[i];
        mx=max(mx,cnt);
    }
    cout << mx << '\n';
}

int main(){
    cout << fixed << setprecision(8);
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

fever.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("Ofast")
      | 
fever.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
fever.cpp: In function 'int main()':
fever.cpp:163:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:164:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 212 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 3 ms 212 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 212 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 212 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 212 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 212 KB Output isn't correct
34 Halted 0 ms 0 KB -