# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1228674 | AlperenT_ | Prize (CEOI22_prize) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e6 + 10 , lg = 25 , maxk = 100 + 10 , inf = 1e9+ 10 , mod = 1e9 + 9 ;
vector <int> G[2][maxn];
int p[2][maxn][lg+1] , d[2][maxn] ;;
int r1 , r2 , n , q , t ,k ;
int lca(int t , int v, int u){
if(d[t][v] > d[t][u])swap(v,u) ;
rep(i , 0 ,lg){
if((d[t][u]-d[t][v])>>i&1){
u = p[t][u][i] ;
}
}
per(i , lg ,0){
if(p[t][v][i] != p[t][u][i]){
v = p[t][v][i] ;
u = p[t][u][i] ;
}
}
if(v==u)return v;
return p[t][v][0];
}
int st[2][maxn] , cnt =1 ;
void dfs(int t , int v , int par=-1){
if(par == -1)par= v;
p[t][v][0] = par;
st[t][v] = cnt;cnt++ ;
rep(i , 1 ,lg)p[t][v][i] = p[t][p[t][v][i-1]][i-1] ;
for(int u : G[t][v]){
d[t][u] = d[t][v]+1;
dfs(t , u , v) ;
}
}
vector <int> a ;
void dfs2(int v){
if(sz(a) < k){
a.pb(v);
}
for(int u : G[0][v]){
dfs2(u);
}
}
vector <pii> T[2][maxn] ;
void add(int t ,int a , int b , int s){// d[b] - d[a] = s
T[t][a].pb({b,s});
T[t][b].pb({a,-s}) ;
}
int D[2][maxn], mark[2][maxn] ;;
void dfs3(int t ,int v){
mark[t][v] =1 ;
for(auto [u,w] : T[t][v]){
if(mark[t][u] == 1)continue ;
D[t][u] = D[t][v] + w;
dfs3(t , u);
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0) ;
cin>> n >> k >> q >> t ;
rep(i , 1, n){
int v;
cin >> v ;
if(v==-1){
r1 =i ;
}else{
G[0][v].pb(i);
}
}
rep(i ,1 , n){
int v ;cin >> v;
if(v==-1){
r2 =i ;
}else{
G[1][v].pb(i) ;
}
}
rep(i ,1 , k)cout << i << " " ;
cout << endl ;
cout << "!" << endl ;
rep(i ,1, t)[
int x, y ;
cin >> x >> y ;
cout << 0 << " " << 0 << "\n";
]
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
10 0 0 1
0 3 13 5
2 1
1 4
2 4
*/