4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс

Есеп E. НурлашКО

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

АланашКО мен НурлашКО графом ойнап жатыр, сол себепті сіздің көмегіңіз қажет. Ойын бағытталған, циклдік емес $G$ графынан басталады. Алғашында граф $n$ шыңнан тұрады және граф қабырғасыз болып келеді. Ойын барысында ойнаушылар $q$ операциялар орындайды. Операциялар түрлері осындай:

1. $u_i$ шыңынан $v_i$ шыңына бағытталған қабырға жасау.
2. 1-ші шыңнан $x_i$ шыңына дейін бағытталған қабырғалар арқылы жол табылса, $x_i$ шығарыңыз, табылмаса $0$ шығарыңыз.

Әр операциядан кейін граф циклсыз болатынына кеппілдік беріледі.

Формат входного файла

Бірінші жолда үш бүтін сан $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — шыңдар саны, операциялар саны мен константалық сан енгізіледі. Келесі $q$ жол әр операцияның сипаттамасын береді.

1. Бірінші түрлі операция осылай сипатталады: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
2. Екінші түрлі операция осылай сипатталады: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.

Назар аударыңыз, бірінші операцияға арналған $u_i$, $v_i$ шыңдар номерлері мен екінші операцияға арналған $x_i$ шыңының номері кодталған болып келеді, және оларды алу үшін осындай тағы операциялар орындау қажет: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} $lastans$ — соңғы $2$ операциясынан шыққан жауап (алғашында $lastans$ $0$-тең). Мына жерде $\oplus$ аралас немесе операциясын білдіреді. Осы операция заманғы бағдарламалау тілдерінде ба, мысалға, C++ және Java — ^ арқылы белгіленген, Pascal — $xor$ арқылы. $a \mod b$ операциясы $a$-ның $b$-ға бөлгендегі қалдығын береді. Есепте кемінде бір екінші түрлі операция келетініне кепілдік беріледі. Аралас НЕМЕСЕ($xor$) операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $xor$ $Y$ = $68_{10}$ = $1000100_{2}$.

Формат выходного файла

Әр екінші түрлі операцияның жауабын бөлек жолға шығарыңыз.

Система оценки

Есеп 5 бөлімнен тұрады:

1. Шарттағы мысалдар. $0$ ұпайға бағаланады.
2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. $11$ ұпайға бағаланады.
3. $n, q <= 10^3$. $18$ ұпайға бағаланады.
4. $t = 0$. $39$ ұпайға бағаланады.
5. Есептің толық шарттары. $32$ ұпайға бағаланады.

Примеры:

Вход

5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3

Ответ

1
0
2
0
4

Вход

5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3

Ответ

1
0
2
0
4

( Zharaskhan Aman )

Комментарий/решение

кодты корсету/жасыру

#include <bits/stdc++.h>
using namespace std;
vector < long long > g[1000005];
bool used[1000005];
void dfs(long long n){
    used[n]=1;
    for(int j=0;j<g[n].size();j++){
        long long to=g[n][j];
        dfs(to);
    }
}
int main(){
    long long n,q,t;
    scanf("%I64d%I64d%I64d", &n,&q,&t);
    long long lastans=0;
    for(int i=1;i<=q;i++){
        long long l;
        scanf("%I64d",&l);
        if(l==1){
            long long a,b;
            scanf("%I64d%I64d", &a,&b);
            long long u=((a^(t*lastans))%n)+1,v=((b^(t*lastans))%n)+1;
            g[u].push_back(v);
        }
        else {
            long long a;
            scanf("%I64d", &a);
            long long x=((a^(t*lastans))%n)+1;
            if(used[x]==1){
                lastans=x;
                printf("%I64d\n", lastans);
                continue;
            }
            dfs(1);
            if(used[x]==1){
                lastans=x;
                printf("%I64d\n", lastans);
            }
            else {
                lastans=0;
                printf("%I64d\n", lastans);
            }
        }

    }
}

кодты корсету/жасыру

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector < ll > g[ 2000010 ];
bool used[ 2000010 ];
void dfs(ll x){
    while (!g[x].empty()) {
        int to = g[x].back();
        g[x].pop_back();
        if (used[to]) {
            continue;
        }
        else {
            used[to] = 1;
            dfs (to);
        }
    }
}
void qaz(ll u,ll v){
    if(used[v]==1)return ;
    else if(used[u]==1  ){
        used[v]=1;
        dfs(v);
    }
    else {
        g[u].push_back(v);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n,q,t;
    cin>>n>>q>>t;
    ll lastans=0;
    used[1]=1;
    for(int i=1;i<=q;i++){
        ll l;
        cin>>l;
        if(l==1){
            ll a,b;
            cin>>a>>b;
            ll u=((a^(t*lastans))%n)+1,v=((b^(t*lastans))%n)+1;
            qaz(u,v);
        }
        else {
            ll a;
            cin>>a;
            ll x=((a^(t*lastans))%n)+1;
            if(used[x]==1){
                lastans=x;
                cout<<lastans<<"\n";
            }
            else {
                lastans=0;
                cout<<lastans<<"\n";
            }
        }

    }
}

Мое решение

кодты корсету/жасыру

#include<bits/stdc++.h>

using namespace std;

#define ss second
#define ff first
#define int long long
#define pb push_back


const int N = 2e6 + 51 + 51, MOD = 1e9 + 7, mod = 998244353, INF = 3e18;

mt19937 Flash_new_51(51515);

using vi = vector <int>
using vp = vector <pair <int, int>>

vi g[N];
int color[N];

void dfs (int v) {
    color[v] = 1;
    for (auto to : g[v]) {
        if (!color[to]) dfs(to);
    }
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, t, q, ans;
    cin >> n >> q >> t;
    color[1] = 1;
    while (q--) {
          int o;
          cin >> o;
          if (o == 1) {
             int v, u, a, b;
             cin >> a >> b;
             u = (a ^ (t * ans)) % n + 1, v = (b ^ (t * ans)) % n + 1;
             if (color[u] && !color[v]) {
                dfs(v);
             }
             g[u].pb(v);
          }
          else {
             int a;
             cin >> a;
             a = (a ^ (t * ans)) % n + 1;
             ans = color[a];
             if (ans) ans = a;
             else ans = 0;
             cout << ans << "\n";
          }
    }
}

кодты корсету/жасыру

#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
int n, q, t, lastans;
vector<int> g[1000005];
bitset<1000005> w;
void dfs(int v) {
  w[v] = 1;
  for (auto to : g[v])
    if (!w[to]) dfs(to);
}
int main() {
  speed;
  oprecision;
  // code
  cin >> n >> q >> t;
  w[1] = 1;
  while (q--) {
    int type, a, b;
    cin >> type;
    if (type == 1) {
      cin >> a >> b;
      int u = ((a ^ (t * lastans)) % n) + 1;
      int v = ((b ^ (t * lastans)) % n) + 1;
      if (w[u] && !w[v]) dfs(v);
      g[u].pb(v);
    }
    if (type == 2) {
      cin >> a;
      int x = ((a ^ (t * lastans)) % n) + 1;
      lastans = (w[x] ? x : 0);
      cout << lastans << "\n";
    }
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}