QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85133#5110. Splitstreamyunny_worldWA 5ms4272kbC++142.5kb2023-03-07 00:10:532023-03-07 00:10:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 00:10:56]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4272kb
  • [2023-03-07 00:10:53]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define X first
#define Y second
#define all(v) v.begin(),v.end()
using namespace std;
const ll INF = 9876543210;
const ll MOD = 1e9 + 7;
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

ll m, n, q;
ll mxnode;
ll sz[20005];
pll from[20005]; // {S로부터 오면 1/M으로부터 오면 2, S왼쪽에서 오면 1/S오른쪽에서 오면 2} 
pll fromx[20005]; // 왼, 오

ll getSz(ll x)
{
    ll& ret = sz[x];
    if (ret != -1) return ret;
    if (x == 1) return ret = m;
    if (from[x].X == 1)
    {
        if (from[x].Y == 1) ret = sz[fromx[x].X] / 2 + sz[fromx[x].X] % 2;
        else ret = sz[fromx[x].X] / 2;
    }
    else ret = sz[fromx[x].X] + sz[fromx[x].Y];
    return ret;
}

ll go(ll x, ll k)
{
    //cout << x << ' ' << k << '\n';
    if (k > sz[x]) return -1;
    if (x == 1) return k;
    if (from[x].X == 1)
    {
        if (from[x].Y == 1) return go(fromx[x].X, 2 * k - 1);
        else return go(fromx[x].X, 2 * k);
    }
    else
    {
        ll mn = min(sz[fromx[x].X], sz[fromx[x].Y]);
        if (k <= 2 * mn)
        {
            if (k % 2) return go(fromx[x].X, (k + 1) / 2);
            else return go(fromx[x].Y, k / 2);
        }
        else
        {
            if (sz[fromx[x].X] == mn) return go(fromx[x].Y, k - mn);
            else return go(fromx[x].X, k - mn);
        }
    }
}

void solve()
{
    cin >> m >> n >> q;
    for (int i = 0; i < n; i++)
    {
        char t; ll x, y, z; cin >> t >> x >> y >> z;
        mxnode = max(mxnode, max(x, max(y, z)));
        if (t == 'S')
        {
            from[y] = { 1, 1 };
            from[z] = { 1, 2 };
            fromx[y] = fromx[z] = {x, 0};
        }
        else
        {
            from[z].X = 2;
            fromx[z] = { x, y };
        }
    }
    memset(sz, -1, sizeof(sz));
    for (int i = 1; i <= mxnode; i++)
    {
        sz[i] = getSz(i);
        //cout << sz[i] << ' ';
    }
    while (q--)
    {
        ll x, k; cin >> x >> k;
        ll res = go(x, k);
        if (res == -1) cout << "none\n";
        else cout << res << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int tc = 1; //cin >> tc;
    while (tc--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

input:

5 8 26
M 8 9 13
S 2 4 5
S 1 2 3
M 6 5 8
S 4 9 10
S 10 14 15
S 3 6 7
S 7 11 12
2 3
2 4
3 2
3 3
4 2
4 3
5 1
5 2
6 1
6 2
7 1
7 2
8 2
8 3
9 1
9 2
10 1
10 2
11 1
11 2
12 1
13 3
13 4
14 1
14 2
15 1

output:

5
none
4
none
5
none
3
none
2
none
4
none
3
none
1
none
5
none
4
none
none
3
none
5
none
none

result:

ok 26 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 4272kb

input:

1000000000 8191 1000
S 1 2 3
S 2 4 5
S 3 6 7
S 4 8 9
S 5 10 11
S 6 12 13
S 7 14 15
S 8 16 17
S 9 18 19
S 10 20 21
S 11 22 23
S 12 24 25
S 13 26 27
S 14 28 29
S 15 30 31
S 16 32 33
S 17 34 35
S 18 36 37
S 19 38 39
S 20 40 41
S 21 42 43
S 22 44 45
S 23 46 47
S 24 48 49
S 25 50 51
S 26 52 53
S 27 54 55...

output:

1
3
999999999
499999999
333333331
999999997
499999997
333333329
2
4
1000000000
500000000
333333332
999999998
499999998
333333330
1
5
999999997
499999997
333333329
999999993
499999993
333333325
3
7
999999999
499999999
333333331
999999995
499999995
333333327
2
6
999999998
499999998
333333330
999999994...

result:

ok 1000 lines

Test #3:

score: -100
Wrong Answer
time: 5ms
memory: 4108kb

input:

1000000000 8190 1000
S 1 2 3
M 8193 8194 8192
S 2 4 5
M 8195 8196 8193
S 3 6 7
M 8197 8198 8194
S 4 8 9
M 8199 8200 8195
S 5 10 11
M 8201 8202 8196
S 6 12 13
M 8203 8204 8197
S 7 14 15
M 8205 8206 8198
S 8 16 17
M 8207 8208 8199
S 9 18 19
M 8209 8210 8200
S 10 20 21
M 8211 8212 8201
S 11 22 23
M 821...

output:

none
none
none
none
none
none
none
none
1
none
3
none
999999999
none
499999999
none
333333331
none
999999997
none
499999997
none
333333329
none
2
none
4
none
1000000000
none
500000000
none
333333332
none
999999998
none
499999998
none
333333330
none
1
none
5
none
999999997
none
499999997
none
3333333...

result:

wrong answer 1st lines differ - expected: '1', found: 'none'