oj.uz

Submission #980326

# Submission time Handle Problem Language Result Execution time Memory
980326 2024-05-12T05:04:55 Z t9unkubj Game (APIO22_game) C++17
12 / 100
 4000 ms 748 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_;
void init(int n,int k){
    g=inv=vvi(n);
    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){
    g[u].pb(v);
    rep(i,k_){
        dbg(i);
        vi seen(n_);
        int ans=0;
        auto dfs=[&](auto&dfs,int u)->void{
            if(ans)return;
            for(auto x:g[u]){
                if(!seen[x]){
                    seen[x]=1;
                    dfs(dfs,x);  
                }if(x==i){
                    ans=1;
                    return;
                }
            }
        };seen[i]=1;dfs(dfs,i);
        if(ans)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)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:168:5: note: in expansion of macro 'rep'
  168 |     rep(i,k_){
      |     ^~~
game.cpp:6:18: warning: statement has no effect [-Wunused-value]
    6 | #define dbg(...) 199958
      |                  ^~~~~~
game.cpp:169:9: note: in expansion of macro 'dbg'
  169 |         dbg(i);
      |         ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 12 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 1 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 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 5 ms 444 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 12 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 1 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 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 5 ms 444 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 36 ms 500 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 974 ms 520 KB Output is correct
25 Correct 2811 ms 748 KB Output is correct
26 Correct 3410 ms 496 KB Output is correct
27 Execution timed out 4064 ms 516 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 12 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 1 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 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 5 ms 444 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 36 ms 500 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 974 ms 520 KB Output is correct
25 Correct 2811 ms 748 KB Output is correct
26 Correct 3410 ms 496 KB Output is correct
27 Execution timed out 4064 ms 516 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 12 ms 440 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 12 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 1 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 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 5 ms 444 KB Output is correct
18 Correct 2 ms 344 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 36 ms 500 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 974 ms 520 KB Output is correct
25 Correct 2811 ms 748 KB Output is correct
26 Correct 3410 ms 496 KB Output is correct
27 Execution timed out 4064 ms 516 KB Time limit exceeded
28 Halted 0 ms 0 KB -