# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
233274 |
2020-05-20T08:19:34 Z |
VEGAnn |
Tenis (COI19_tenis) |
C++14 |
|
165 ms |
23280 KB |
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 100100;
const int md = int(1e9) + 7;
vector<int> g[N], ts, gr[N], co[N];
int loc[3][N], n, q, a[3][N], kol, comp[N], in[N];
bool mrk[N];
void top_sort(int v){
if (mrk[v]) return;
mrk[v] = 1;
for (int u : g[v])
top_sort(u);
ts.PB(v);
}
void dfs(int v){
if (comp[v] >= 0) return;
comp[v] = kol;
for (int u : gr[v])
dfs(u);
}
void build(){
for (int i = 0; i < n; i++) {
g[i].clear();
gr[i].clear();
comp[i] = -1;
}
for (int tp = 0; tp < 3; tp++)
for (int i = 1; i < n; i++) {
g[a[tp][i - 1]].PB(a[tp][i]);
gr[a[tp][i]].PB(a[tp][i - 1]);
}
fill(mrk, mrk + n, 0);
ts.clear();
for (int i = 0; i < n; i++){
if (mrk[i]) continue;
top_sort(i);
}
reverse(all(ts));
fill(mrk, mrk + n, 0);
kol = 0;
for (int v : ts){
if (comp[v] >= 0) continue;
dfs(v);
kol++;
}
for (int tp = 0; tp < 3; tp++)
for (int i = 1; i < n; i++) {
int cur = comp[a[tp][i]];
if (comp[a[tp][i - 1]] == cur) continue;
if (in[cur] == 0)
kol--;
in[cur]++;
}
fill(mrk, mrk + n, 0);
if (kol != 1) return;
int cur = -1;
for (int i = 0; ; i++)
if (in[i] == 0){
cur = i;
break;
}
assert(cur != -1);
for (int i = 0; i < n; i++)
if (comp[i] == cur)
mrk[i] = 1;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> q;
for (int tp = 0; tp < 3; tp++)
for (int i = 0; i < n; i++){
int x; cin >> x;
x--;
loc[tp][x] = i;
a[tp][i] = x;
}
build();
for (; q; q--){
int tp; cin >> tp;
if (tp == 1){
int x; cin >> x; x--;
cout << (mrk[x] ? "DA\n" : "NE\n");
} else {
int x, y; cin >> tp >> x >> y;
tp--; x--; y--;
swap(loc[tp][x], loc[tp][y]);
swap(a[tp][loc[tp][x]], a[tp][loc[tp][y]]);
build();
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
18520 KB |
Output is correct |
2 |
Correct |
144 ms |
22252 KB |
Output is correct |
3 |
Correct |
139 ms |
22428 KB |
Output is correct |
4 |
Correct |
129 ms |
23280 KB |
Output is correct |
5 |
Correct |
145 ms |
21236 KB |
Output is correct |
6 |
Correct |
147 ms |
22384 KB |
Output is correct |
7 |
Correct |
136 ms |
21108 KB |
Output is correct |
8 |
Correct |
138 ms |
22644 KB |
Output is correct |
9 |
Correct |
146 ms |
22256 KB |
Output is correct |
10 |
Correct |
143 ms |
22004 KB |
Output is correct |
11 |
Correct |
147 ms |
21364 KB |
Output is correct |
12 |
Correct |
150 ms |
22644 KB |
Output is correct |
13 |
Correct |
165 ms |
22384 KB |
Output is correct |
14 |
Correct |
149 ms |
22772 KB |
Output is correct |
15 |
Correct |
157 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |