| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35016 |
2017-11-17T09:54:59 Z |
buichitrung2001 |
스파이 (JOI13_spy) |
C++14 |
|
46 ms |
9852 KB |
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define Tpair pair <int, int>
#define gc getchar
#define pc putchar
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9 + 1;
int n, m, i, T, par[3][2005], child[3][2005], pos[3][2005], cnt[3], p[3], root[3], s[3],
ans[2005], pos2[3][2005], dem;
bitset <5000> sum[3][2005], bit[3], res[3][2005];
vector <int> v[3][2005];
inline void read(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for (;((c<48 || c>57) && c != '-') ;c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
inline void writeln(int x){
char buffor[21];
register int i=0;
int neg=0; if (x<0) {neg=1; x= -x;}
do{
buffor[i++]=(x%10)+'0';
x/=10;
} while(x);
i--;
if (neg) pc('-');
while(i>=0) pc(buffor[i--]);
pc('\n');
}
void Dfs (int x, int pre, int idx)
{
par[idx][x] = pre;
child[idx][x] = 1;
pos[idx][x] = ++cnt[idx];
pos2[idx][cnt[idx]] = x;
for (int j : v[idx][x])
if (!par[idx][j])
{
Dfs (j, x, idx);
child[idx][x] += child[idx][j];
}
}
void Init()
{
//cin >> n >> m;
read(n); read(m);
for (int i = 1; i <= n; ++i)
{
//cin >> p[1] >> p[2];
read(p[1]); read(p[2]);
if (p[1] != 0) v[1][p[1]].push_back (i);
if (p[2] != 0) v[2][p[2]].push_back (i);
if (p[1] == 0) root[1] = i;
if (p[2] == 0) root[2] = i;
}
Dfs (root[1], root[1], 1);
Dfs (root[2], root[2], 2);
//for (int i = 1; i <= n; ++i) cout << i << " " << par[1][i] << " " << child[1][i] << " " << pos[1][i] << '\n';
//for (int i = 1; i <= n; ++i) cout << i << " " << par[2][i] << " " << child[2][i] << " " << pos[2][i] << '\n';
}
void Reset()
{
for (int i = 1; i <= n; ++i)
{
bit[1] ^= sum[1][i];
bit[2] ^= sum[2][i];
res[1][i] = bit[1];
res[2][i] = bit[2];
//cout << sum[1][i] << endl << sum[2][i] << endl;
}
for (int i = 1; i <= n; ++i) ans[i] = (res[1][pos[1][i]] & res[2][pos[2][i]]).count();
dem = 0;
for (int i = 1; i <= n; ++i)
{
res[1][i].reset();
res[2][i].reset();
sum[1][i].reset();
sum[2][i].reset();
}
bit[1].reset(); bit[2].reset();
}
void Solve()
{
for (int i = 1; i <= m; ++i)
{
//cin >> s[1] >> s[2];
read(s[1]); read(s[2]);
sum[1][pos[1][s[1]]][dem] = 1;
sum[2][pos[2][s[2]]][dem] = 1;
sum[1][pos[1][s[1]] + child[1][s[1]]][dem] = 1;
sum[2][pos[2][s[2]] + child[2][s[2]]][dem] = 1;
//if (dem == 3) Reset();
++dem;
}
Reset();
for (int i = 1; i <= n; ++i) writeln(ans[i]);
}
int main()
{
//freopen ("spy.inp", "r", stdin);
//freopen ("spy.out", "w", stdout);
Init();
Solve();
}
// Date 15 Month 11 Year 2017
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 4 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 5 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 6 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 7 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 8 |
Correct |
0 ms |
9688 KB |
Output is correct |
| 9 |
Correct |
0 ms |
9688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9852 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9848 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9688 KB |
Output is correct |
| 4 |
Correct |
3 ms |
9688 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
6 ms |
9820 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
9852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
