QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85133 | #5110. Splitstream | yunny_world | WA | 5ms | 4272kb | C++14 | 2.5kb | 2023-03-07 00:10:53 | 2023-03-07 00:10:56 |
Judging History
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'