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

Задача E. НурлашКО

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

1 секунда

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

256 мегабайт

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:

1. Добавить ориентированное ребро из вершины $u_i$ в вершину $v_i$.
2. Вывести $x_i$, если существует ориентированный путь из вершины 1 в вершину $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$ для запросов типа $1$ и вершина $x_i$ для запросов типа $2$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
$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$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как $xor$. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$. Гарантируется, что во входных данных присутствует хотя бы один запрос типа $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;
}