結果
| 問題 |
No.1914 Directed by Two Sequences
|
| ユーザー |
 Guo yinhe
|
| 提出日時 | 2025-05-21 21:48:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 4,782 bytes |
| コンパイル時間 | 3,016 ms |
| コンパイル使用メモリ | 224,168 KB |
| 実行使用メモリ | 44,356 KB |
| 最終ジャッジ日時 | 2025-05-21 21:49:00 |
| 合計ジャッジ時間 | 30,437 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | RE * 38 |
コンパイルメッセージ
main.cpp: In function ‘void SOLVER::MAIN()’:
main.cpp:97:35: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
97 | for(int v: g[u]) printf("%d %d\n", t[u][0], t[v][0]);
| ~^
| |
| int
| %lld
main.cpp:97:38: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
97 | for(int v: g[u]) printf("%d %d\n", t[u][0], t[v][0]);
| ~^
| |
| int
| %lld
main.cpp:99:22: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
99 | printf("%d %d\n", t[u][j], t[u][(j + 1) % t[u].size()]);
| ~^
| |
| int
| %lld
main.cpp:99:25: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
99 | printf("%d %d\n", t[u][j], t[u][(j + 1) % t[u].size()]);
| ~^
| |
| int
| %lld
ソースコード
//Date: 2025-05-20 11:40:53
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define P emplace_back
#define CLEAR(a,v) memset(a,(v),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
bool MBE;
namespace SOLVER {
const int N = 1e5 + 5, inf = 1e9;
int n, m, a[N], b[N], id[N], tim, pos[N], bel[N], deg[N];
set<int> st[N]; map<int, int> mp[N]; queue<int> q; vector<int> t[N], g[N];
struct Seg {
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
int mx[N * 4], mn[N * 4]; void clear() {rep(i, 0, n * 4) mx[i] = -inf, mn[i] = inf;}
void update(int p, int l, int r, int x, int v1 = -inf, int v2 = inf) {
if(l == r) return mx[p] = v1, mn[p] = v2, void();
x <= mid ? update(ls, l, mid, x, v1, v2) : update(rs, mid + 1, r, x, v1, v2);
mx[p] = max(mx[ls], mx[rs]), mn[p] = min(mn[ls], mn[rs]);
}
int query1(int p, int l, int r, int x, int lim) {
if(mx[p] <= lim) return -inf; if(l == r) return x <= l ? mx[p] : -inf;
if(x <= mid && mx[ls] > lim) {int v = query1(ls, l, mid, x, lim); if(v != -inf) return v;}
return query1(rs, mid + 1, r, x, lim);
}
int query2(int p, int l, int r, int x, int lim) {
if(mn[p] >= lim) return +inf; if(l == r) return x <= l ? mn[p] : +inf;
if(x <= mid && mn[ls] < lim) {int v = query2(ls, l, mid, x, lim); if(v != +inf) return v;}
return query2(rs, mid + 1, r, x, lim);
}
} t1, t2;
void dfs1(int u) {
t1.update(1, 1, n * 2, a[u]), t2.update(1, 1, n * 2, b[u]);
// cerr << u << endl;
int lim1 = a[u], lim2 = b[u];
while(1) {
int x = t2.query1(1, 1, n * 2, lim1 + 1, u); if(x == -inf) break; assert(b[x] > lim1 && x > u); lim1 = b[x];
if(!st[u].count(x)) dfs1(x);
}
while(1) {
int x = t1.query2(1, 1, n * 2, lim2 + 1, u); if(x == +inf) break; assert(a[x] > lim2 && x < u); lim2 = a[x];
if(!st[u].count(x)) dfs1(x);
}
id[u] = ++tim;
}
void dfs2(int u) {
t1.update(1, 1, n * 2, a[u]), t2.update(1, 1, n * 2, b[u]);
// cerr<< u << endl;
bel[u] = tim, t[tim].P(u), id[u] = 0; int lim1 = a[u], lim2 = b[u];
while(1) {
int x = t2.query1(1, 1, n * 2, lim1 + 1, u); if(x == -inf) break; assert(b[x] > lim1 && x > u); lim1 = b[x];
if(!st[u].count(x)) dfs2(x);
}
while(1) {
int x = t1.query2(1, 1, n * 2, lim2 + 1, u); if(x == +inf) break;
// if(!(a[x] > lim2 && x < u)) cerr << u << ' ' << x << ' ' << a[x] << ' ' << lim2 << endl;
assert(a[x] > lim2 && x < u); lim2 = a[x];
if(!st[u].count(x)) dfs2(x);
}
}
bool chk(int x, int y) {return mp[x][y] != t[x].size() * t[y].size();}
void MAIN() {
n = rd(), m = rd(); rep(i, 1, n) a[i] = rd(); rep(i, 1, n) b[i] = rd();
rep(i, 1, m) {int u = rd(), v = rd(); st[u].insert(v), st[v].insert(u);}
t1.clear(), t2.clear(); rep(i, 1, n) t1.update(1, 1, n * 2, a[i], i, i), t2.update(1, 1, n * 2, b[i], i, i);
rep(i, 1, n) if(!id[i]) dfs1(i); rep(i, 1, n) pos[id[i]] = i;
// rep(i, 1, n) cerr << id[i] << ' '; cerr << endl;
rep(i, 1, n) a[i] = 2 * n + 1 - a[i], b[i] = 2 * n + 1 - b[i];
t1.clear(), t2.clear(); rep(i, 1, n) t1.update(1, 1, n * 2, a[i], i, i), t2.update(1, 1, n * 2, b[i], i, i);
tim = 0; per(i, n, 1) if(id[pos[i]]) tim++, dfs2(pos[i]);
// rep(i, 1, n) cerr << bel[i] << ' '; cerr << endl;
rep(u, 1, n) for(int v: st[u]) if(bel[u] != bel[v]) mp[bel[u]][bel[v]]++;
per(i, tim, 1) {
stack<int> res;
while(q.size()) {
int u = q.front(); q.pop(); assert(deg[u] >= 0); if(deg[u]) continue;
if(chk(i, u)) g[i].P(u), deg[u]++;
else {res.push(u); for(int v: g[u]) if(--deg[v] == 0) q.push(v);}
}
while(res.size()) {int u = res.top(); res.pop(); q.push(u); for(int v: g[u]) deg[v]++;}
q.push(i);
}
int ans = 0; rep(u, 1, tim) {ans += g[u].size(); if(t[u].size() != 1) ans += t[u].size();}
cout << ans << endl;
rep(u, 1, tim) {
for(int v: g[u]) printf("%d %d\n", t[u][0], t[v][0]);
if(t[u].size() != 1) rep(j, 0, t[u].size() - 1)
printf("%d %d\n", t[u][j], t[u][(j + 1) % t[u].size()]);
}
}
}
bool MED;
signed main() {
//freopen(".in","r",stdin);freopen(".out","w",stdout);
for(int tt=1;tt;tt--) SOLVER::MAIN();
cerr<<(&MBE-&MED)/1024<<" KB, "<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
return 0;
}