oj.uz

답안 #980354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
980354 2024-05-12T05:53:41 Z t9unkubj 게임 (APIO22_game) C++17
60 / 100
 4000 ms 35548 KB 
#pragma GCC optimize("O3")
#ifdef t9unkubj
#include "debug.cpp"
#else
#define dbg(...) 199958
#endif

using namespace std;
#include<bits/stdc++.h>
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T>using vvvc=vvc<vc<T>>;
using vi=vc<int>;
using vvi=vc<vi>;
using vvvi=vc<vvi>;
using vl=vc<ll>;
using vvl=vc<vl>;
using vvvl=vc<vvl>;
template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;
template<class T>using bipq=priority_queue<T>;
#define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll (i)=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll (i)=(n);i>=(m);i--)
#define drep(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define is insert
#define bg begin()
#define ed end()
void scan(int&a) { cin >> a; }
void scan(ll&a) { cin >> a; }
void scan(string&a) { cin >> a; }
void scan(char&a) { cin >> a; }
void scan(uint&a) { cin >> a; }
void scan(ull&a) { cin >> a; }
void scan(bool&a) { cin >> a; }
void scan(ld&a){ cin>> a;}
template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }
void read() {}
template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);
#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);
#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);
void print(int a) { cout << a; }
void print(ll a) { cout << a; }
void print(string a) { cout << a; }
void print(char a) { cout << a; }
void print(uint a) { cout << a; }
void print(bool a) { cout << a; }
void print(ull a) { cout << a; }
void print(ld a){ cout<< a; }
template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}
void PRT() { cout <<endl; return ; }
template<class T> void PRT(T a) { print(a); cout <<endl; return; }
template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
void YesNo(bool b){
    cout<<(b?"Yes":"No")<<endl;
}
void Yes(){
    cout<<"Yes"<<endl;
}
void No(){
    cout<<"No"<<endl;
}
template<class T>
int popcount(T n){
    return __builtin_popcount(n);
}
template<class T>
T sum(vc<T>&a){
    return accumulate(all(a),T(0));
}
template<class T>
T max(vc<T>&a){
    return *max_element(all(a));
}
template<class T>
T min(vc<T>&a){
    return *min_element(all(a));
}
template<class T>
void unique(vc<T>&a){
    a.erase(unique(all(a)),a.end());
}
vvi readgraph(int n,int m,int off = -1){
    vvi g(n);
    rep(i, m){
        int u,v;
        cin>>u>>v;
        u+=off,v+=off;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}
vvi readtree(int n,int off=-1){
    return readgraph(n,n-1,off);
}
template<class T>
vc<T> presum(vc<T> &a){
    vc<T> ret(a.size()+1);
    rep(i,a.size())ret[i+1]=ret[i]+a[i];
    return ret;
}
template<class T, class F>
vc<T> &operator+=(vc<T> &a,F b){
    for (auto&v:a)v += b;
    return a;
}
template<class T, class F>
vc<T> &operator-=(vc<T>&a,F b){
    for (auto&v:a)v-=b;
    return a;
}
template<class T, class F>
vc<T> &operator*=(vc<T>&a,F b){
    for (auto&v:a)v*=b;
    return a;
}
double pass_time=0;
vvi g;
vvi inv;
int n_;
int k_;
vi dp;
void init(int n,int k){
    g=inv=vvi(n);
    dp=vi(n,1e9);
    rep(i,k-1)dp[i]=i+1;
    k_=k;
    n_=n;
    rep(i,k-1)g[i].pb(i+1),inv[i+1].pb(i);
}
int add_teleporter(int u,int v){
    inv[v].pb(u);
    g[u].pb(v);
    if((v<k_||dp[v]<k_)&&chmin(dp[u],min(v,dp[v]))){
        queue<int>que;
        que.push(u);
        while(que.size()){
            auto p=que.front();que.pop();
            for(auto x:inv[p]){
                if((p<k_||dp[p]<k_)&&chmin(dp[x],min(p,dp[p]))){
                    que.push(x);
                }
            }
        }
        rep(i,k_){
            if(dp[i]<=i)return 1;
        }
    }
    return 0;
}

Compilation message

game.cpp: In function 'vvi readgraph(int, int, int)':
game.cpp:28:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
      |                         ^
game.cpp:122:5: note: in expansion of macro 'rep'
  122 |     rep(i, m){
      |     ^~~
game.cpp: In function 'vc<T> presum(vc<T>&)':
game.cpp:28:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
      |                         ^
game.cpp:137:5: note: in expansion of macro 'rep'
  137 |     rep(i,a.size())ret[i+1]=ret[i]+a[i];
      |     ^~~
game.cpp: In function 'void init(int, int)':
game.cpp:28:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
      |                         ^
game.cpp:164:5: note: in expansion of macro 'rep'
  164 |     rep(i,k-1)dp[i]=i+1;
      |     ^~~
game.cpp:28:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
      |                         ^
game.cpp:167:5: note: in expansion of macro 'rep'
  167 |     rep(i,k-1)g[i].pb(i+1),inv[i+1].pb(i);
      |     ^~~
game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:28:25: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)
      |                         ^
game.cpp:183:9: note: in expansion of macro 'rep'
  183 |         rep(i,k_){
      |         ^~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 3 ms 856 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 1 ms 540 KB Output is correct
29 Correct 2 ms 344 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 3 ms 856 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 1 ms 540 KB Output is correct
29 Correct 2 ms 344 KB Output is correct
30 Correct 14 ms 2904 KB Output is correct
31 Correct 3 ms 2392 KB Output is correct
32 Correct 15 ms 3764 KB Output is correct
33 Correct 18 ms 3928 KB Output is correct
34 Correct 476 ms 4096 KB Output is correct
35 Correct 188 ms 4388 KB Output is correct
36 Correct 31 ms 4072 KB Output is correct
37 Correct 21 ms 3928 KB Output is correct
38 Correct 26 ms 3752 KB Output is correct
39 Correct 32 ms 3864 KB Output is correct
40 Correct 394 ms 4172 KB Output is correct
41 Correct 93 ms 4244 KB Output is correct
42 Correct 68 ms 4176 KB Output is correct
43 Correct 34 ms 4792 KB Output is correct
44 Correct 247 ms 4184 KB Output is correct

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 3 ms 856 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 1 ms 540 KB Output is correct
29 Correct 2 ms 344 KB Output is correct
30 Correct 14 ms 2904 KB Output is correct
31 Correct 3 ms 2392 KB Output is correct
32 Correct 15 ms 3764 KB Output is correct
33 Correct 18 ms 3928 KB Output is correct
34 Correct 476 ms 4096 KB Output is correct
35 Correct 188 ms 4388 KB Output is correct
36 Correct 31 ms 4072 KB Output is correct
37 Correct 21 ms 3928 KB Output is correct
38 Correct 26 ms 3752 KB Output is correct
39 Correct 32 ms 3864 KB Output is correct
40 Correct 394 ms 4172 KB Output is correct
41 Correct 93 ms 4244 KB Output is correct
42 Correct 68 ms 4176 KB Output is correct
43 Correct 34 ms 4792 KB Output is correct
44 Correct 247 ms 4184 KB Output is correct
45 Correct 203 ms 27888 KB Output is correct
46 Correct 9 ms 16032 KB Output is correct
47 Correct 8 ms 15960 KB Output is correct
48 Correct 218 ms 35548 KB Output is correct
49 Correct 202 ms 34944 KB Output is correct
50 Execution timed out 4096 ms 34920 KB Time limit exceeded
51 Halted 0 ms 0 KB -