QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464275 | #5523. Graph Problem With Small $n$ | BalintR | TL | 1910ms | 49072kb | C++20 | 2.9kb | 2024-07-06 00:01:23 | 2024-07-06 00:01:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}
const int MN = 24;
int n, mask;
int adjMat[MN], iAdjMat[MN], ans[MN];
int dp[1<<(MN-1)], hasDp[1<<(MN-1)];
vi smallPop, eqPop;
bool tmpAns[MN];
bool dfs(int s1, int n1){
if(hasDp[s1] & (1 << n1)) return dp[s1] & (1 << n1);
hasDp[s1] |= 1 << n1;
int adj = adjMat[n1] & s1;
while(adj){
int n2 = __builtin_ctz(adj);
adj ^= 1 << n2;
if(dfs(s1 ^ (1 << n2), n2)){
dp[s1] |= 1 << n1;
return true;
}
}
return false;
}
void solve(){
dp[0] = adjMat[n-1];
for(int s1 : smallPop){
int inc = ~s1 & dp[s1];
#define proc(n1){int flag = (inc >> n1) & 1; dp[s1 | (1 << n1)] |= adjMat[n1] & -flag;}
FR(n1, n-1) proc(n1);
hasDp[s1] = mask;
}
for(int s1 : eqPop) hasDp[s1] = mask;
FR(src, n-1) tmpAns[src] = dfs(mask ^ (1 << src), src);
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> n;
FR(i, n){
string str; cin >> str;
FR(j, n) iAdjMat[i] |= (str[j]-'0') << j;
}
FR(s, 1<<(n-1)){
int pop = __builtin_popcount(s);
if(pop < 10) smallPop.pb(s);
if(pop == 10) eqPop.pb(s);
}
mask = (1<<(n-1))-1;
FR(src, n){
fill_n(dp, 1<<(n-1), 0);
fill_n(hasDp, 1<<(n-1), 0);
vi ord(n);
iota(ALL(ord), 0);
swap(ord[src], ord[n-1]);
ms(adjMat, 0);
FR(i, n) FR(j, n) adjMat[i] |= ((iAdjMat[ord[i]] >> ord[j]) & 1) << j;
solve();
FR(n1, n) if(n1 != src) ans[src] |= tmpAns[ord[n1]] << n1;
}
FR(i, n){
FR(j, n) cout << ((ans[i] >> j) & 1);
cout << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5660kb
input:
4 0110 1010 1101 0010
output:
0001 0001 0000 1100
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 5580kb
input:
6 010001 101000 010100 001010 000101 100010
output:
010001 101000 010100 001010 000101 100010
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 5624kb
input:
4 0111 1011 1101 1110
output:
0111 1011 1101 1110
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 896ms
memory: 46360kb
input:
23 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #5:
score: 0
Accepted
time: 887ms
memory: 47948kb
input:
23 00010100000000000101000 00000000010000000001000 00000000000001000000001 10000000000000000010000 00000000000000000000000 10000000000000000000000 00000001000000000000000 00000010000000000010000 00000000000001000000000 01000000000000000000000 00000000000000000000000 00000000000000000000000 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #6:
score: 0
Accepted
time: 930ms
memory: 49072kb
input:
23 00001000000000000000000 00001000010001000000000 00000000000101000010000 00001000000100000000000 11010000010011000100000 00000000000100000000000 00000000000000000000001 00000000000000000101000 00000000000000000000000 01001000000000101010010 00000000000000000000101 00110100000010001000000 000010000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #7:
score: 0
Accepted
time: 933ms
memory: 48328kb
input:
23 01000000000001101001100 10000001101000000000000 00000100000100010000100 00000000000000001011000 00000100001000000000000 00101000000000001000001 00000000000000000000000 01000000000000000000000 01000000000100000010000 00000000000001000000011 01001000000000010000000 00100000100001000100001 000000000...
output:
00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 00000000000000000000000 000000000000...
result:
ok 23 lines
Test #8:
score: 0
Accepted
time: 1121ms
memory: 48960kb
input:
23 00000000010001001001010 00100010001101110000001 01000001000100110000000 00000011010001101100100 00000000010000010001000 00000000000000001001000 01010001000000000000001 00110010000000000000010 00000000011000100100000 10011000101000100000000 01000000110010101010000 01100000000000000000000 000000000...
output:
01111111110111110110111 10011111110111110110111 10011111110111110110111 11101111110110110110111 11110111110111110110111 11111011110111111111111 11111101110111110110111 11111110110111110110111 11111111010111110110111 11111111100110100110111 00000000000010000010100 11111111110011110110111 111111111111...
result:
ok 23 lines
Test #9:
score: 0
Accepted
time: 1910ms
memory: 47496kb
input:
23 00001000001001000000000 00101100111110100000000 01001000100001011010000 00000000010000010010000 11100001100001000000010 01000010101010100011011 00000100000100100010000 00001000011000000010001 01101100000000011001001 01010001000010011000000 11000101000110001100000 01000010001000000000010 010001000...
output:
00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 00000000000000000000100 000000000000...
result:
ok 23 lines
Test #10:
score: -100
Time Limit Exceeded
input:
23 00001011110010000000001 00000100000011000000100 00010011010100000000011 00100011011001010100100 10000101000110100000000 01001000001010001000100 10110000000110000010000 10111000001100010100010 10000000000010001000110 10110000001110100110001 00010101010100001000000 00101011011000100100011 110011101...