ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#494 | #93. 「NOIP2020」排水系统 | Pigsyy | 0 | 0ms | 0kb | C++23 | 8.4kb | 2025-04-25 16:15:09 | 2025-04-25 16:15:10 |
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
struct _int128 {
unsigned long long low;
long long high;
bool sign;
_int128() {}
_int128(unsigned long long a, long long b, bool c = 1):
low(a), high(b), sign(c) {}
_int128(char a): low(abs(a)), high(0), sign(a >= 0) {}
_int128(unsigned char a): low(a), high(0), sign(1) {}
_int128(short a): low(abs(a)), high(0), sign(a >= 0) {}
_int128(unsigned short a): low(a), high(0), sign(1) {}
_int128(int a): low(abs(a)), high(0), sign(a >= 0) {}
_int128(unsigned int a): low(a), high(0), sign(1) {}
_int128(long long a): low(abs(a)), high(0), sign(a >= 0) {}
_int128(unsigned long long a): low(a), high(0), sign(1) {}
explicit operator char() { return (char)low; }
explicit operator unsigned char() {
unsigned char res = low;
if (!sign) res = -res;
return res;
}
explicit operator short() { return (short)low; }
explicit operator unsigned short() {
unsigned short res = low;
if (!sign) res = -res;
return res;
}
explicit operator int() { return (int)low; }
explicit operator unsigned int() {
unsigned int res = low;
if (!sign) res = -res;
return res;
}
explicit operator long long() { return (long long)low; }
explicit operator unsigned long long() {
unsigned long long res = low;
if (!sign) res = -res;
return res;
}
_int128 operator= (const _int128 &x) {
low = x.low, high = x.high, sign = x.sign;
return (*this);
}
bool operator! () const {
return low == 0 && high == 0;
}
bool operator== (const _int128 &y) const {
auto x = (*this);
return x.sign == y.sign && x.low == y.low && x.high == y.high;
}
bool operator< (const _int128 &y) const {
auto x = (*this);
if (x.sign < y.sign) return 1;
if (x.sign > y.sign) return 0;
if (x.high < y.high) return 1;
if (x.high > y.high) return 0;
if (x.low < y.low) return 1;
if (x.low > y.low) return 0;
return 0;
}
bool operator<= (const _int128 &y) const {
auto x = (*this);
return x < y || x == y;
}
bool operator> (const _int128 &y) const {
auto x = (*this);
return !(x <= y);
}
bool operator>= (const _int128 &y) const {
auto x = (*this);
return !(x < y);
}
_int128 operator- () {
auto t = (*this);
t.sign ^= 1;
return t;
}
_int128 add(_int128 x, _int128 y) {
auto lo = x.low + y.low;
auto hi = x.high + y.high;
hi += lo < x.low;
return _int128(lo, hi);
}
_int128 sub(_int128 x, _int128 y) {
bool neg = false;
if (x < y) swap(x, y), neg = true;
auto lo = x.low - y.low;
auto hi = x.high - y.high;
hi -= x.low < y.low;
return _int128(lo, hi, !neg);
}
_int128 operator+ (_int128 y) {
auto x = (*this);
if (x.sign ^ y.sign) {
if (x < y) swap(x, y);
return sub(x, y);
} else {
auto t = add(x, y);
t.sign ^= !x.sign;
return t;
}
}
_int128 operator+= (const _int128 &x) {
return (*this) = (*this) + x;
}
_int128 operator- (_int128 y) const {
auto x = (*this);
return x + (-y);
}
_int128 operator-= (const _int128 &x) {
return (*this) = (*this) - x;
}
_int128 operator<< (const unsigned long long &y) const {
auto x = (*this);
if (y > 128) return _int128(0, 0);
if (y >= 64) {
return _int128(0, x.low << (y - 64), x.sign);
} else {
_int128 res = x;
unsigned long long t = x.low >> (64 - y);
res.high = (res.high << y) + t;
res.low = res.low << y;
return res;
}
}
_int128 operator<<= (const unsigned long long &y) {
return (*this) = (*this) << y;
}
_int128 operator>> (const unsigned long long &y) const {
auto x = (*this);
if (y > 128) return _int128(0, 0);
if (y >= 64) {
return _int128(x.high >> (y - 64), 0, x.sign);
} else {
_int128 res = x;
unsigned long long t = x.high & ((1ll << y) - 1);
res.low = (res.low >> y) + (t << (64 - y));
res.high = res.high >> y;
return res;
}
}
_int128 operator>>= (const unsigned long long &y) {
return (*this) = (*this) >> y;
}
_int128 operator& (_int128 y) {
auto x = (*this);
if (!x.sign) x.low = ~x.low, x.high = ~x.high;
if (!y.sign) y.low = ~y.low, y.high = ~y.high;
return _int128(x.low & y.low, abs(x.high & y.high), x.sign | y.sign);
}
_int128 operator| (_int128 y) {
auto x = (*this);
if (!x.sign) x.low = ~x.low, x.high = ~x.high;
if (!y.sign) y.low = ~y.low, y.high = ~y.high;
return _int128(x.low | y.low, abs(x.high | y.high), x.sign & y.sign);
}
_int128 operator^ (_int128 y) {
auto x = (*this);
if (!x.sign) x.low = ~x.low, x.high = ~x.high;
if (!y.sign) y.low = ~y.low, y.high = ~y.high;
return _int128(x.low ^ y.low, abs(x.high ^ y.high), !(x.sign ^ y.sign));
}
_int128 operator&= (const _int128 &x) {
return (*this) = (*this) & x;
}
_int128 operator|= (const _int128 &x) {
return (*this) = (*this) | x;
}
_int128 operator^= (const _int128 &x) {
return (*this) = (*this) ^ x;
}
_int128 operator* (const _int128 &y) const {
auto x = (*this);
long long H = x.high * y.low + x.low * y.high, L = 0;
unsigned int LH1 = x.low / (1ll << 32), LH2 = y.low / (1ll << 32);
unsigned int LL1 = x.low, LL2 = y.low;
H += (long long)LH1 * LH2, L += (unsigned long long)LL1 * LL2;
_int128 res = _int128(L, H, !(x.sign xor y.sign));
res += _int128((unsigned long long)LL1 * LH2) << 32;
res += _int128((unsigned long long)LH1 * LL2) << 32;
return res;
}
_int128 operator*= (const _int128 &y) {
return (*this) = (*this) * y;
}
_int128 operator/ (_int128 y) const {
auto x = (*this), z = _int128(1);
while (y <= x) y <<= 1, z <<= 1;
_int128 res = 0;
while (y > 0) {
if (x >= y) {
x -= y;
res |= z;
}
y >>= 1, z >>= 1;
}
res.sign = !(x.sign ^ y.sign);
return res;
}
_int128 operator/= (const _int128 &y) {
return (*this) = (*this) / y;
}
};
#define ll _int128
inline long long read(){
long long x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,in[100001],out[100001],book[100001];
ll xx[100001],yy[100001];
ll gcd(ll x,ll y){
if (x == 0 || y == 0) return x + y;
while (x != y) {
if (x > y) x -= y;
else y -= x;
}
return x;
}
void add(int u,ll x,ll y){
if(y==0)
return;
if(yy[u]==0){
xx[u]=x;
yy[u]=y;
return;
}
ll p1=xx[u]*y+yy[u]*x;
ll p2=yy[u]*y;
ll p3=gcd(p1,p2);
xx[u]=p1/p3;
yy[u]=p2/p3;
return;
}
vector<int> a[500001];
queue<int> q;
void tp(){
for(int i=1;i<=n;i++)
if(!in[i]){
book[i]=1;
q.push(i);
xx[i]=1,yy[i]=1;
}
while(!q.empty()){
int p=q.front();
q.pop();
if(out[p])
continue;
for(int i=0;i<a[p].size();i++){
add(a[p][i],xx[p],yy[p]*(1ll*a[p].size()));
if(book[a[p][i]])
continue;
in[a[p][i]]--;
if(in[a[p][i]]==0){
book[a[p][i]]=1;
q.push(a[p][i]);
}
}
}
return;
}
int main()
{
//freopen("water.in","r",stdin);
//freopen("water.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++){
int d=read();
if(d==0){
out[i]=1;
continue;
}
while(d--){
int v;
v=read();
a[i].push_back(v);
in[v]++;
}
}
tp();
for(int i=1;i<=n;i++){
if(out[i]){
add(i,0,1);
printf("%lld %lld\n",xx[i],yy[i]);
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Time Limit Exceeded
input:
10 1 4 2 3 4 5 3 6 7 8 3 7 10 8 1 7 2 8 10 2 8 9 2 9 8 1 10 1 10 0
output:
result:
Test #2:
score: 0
Time Limit Exceeded
input:
10 1 5 2 3 4 5 7 3 6 7 9 3 7 8 9 3 8 9 6 1 7 2 9 10 2 10 9 0 0 0
output:
result:
Test #3:
score: 0
Time Limit Exceeded
input:
10 1 5 2 3 4 5 8 4 6 8 7 9 2 7 6 4 8 6 9 10 2 9 8 1 10 0 0 1 10 0
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
1000 1 5 2 3 4 5 468 5 6 7 8 9 72 5 10 11 12 13 658 5 14 15 16 17 100 5 18 19 20 21 129 5 22 23 24 2...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
1000 1 5 2 3 4 5 257 5 6 7 8 9 948 5 10 11 12 13 633 5 14 15 16 17 1000 5 18 19 20 21 105 5 22 23 24...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
1000 1 5 2 3 4 5 799 5 6 7 8 9 587 5 10 11 12 13 694 5 14 15 16 17 865 5 18 19 20 21 10 5 22 23 24 2...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
100000 1 5 2 3 4 5 7783 5 6 7 8 9 21991 5 10 11 12 13 45651 5 14 15 16 17 56745 5 18 19 20 21 84002 ...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
100000 1 5 2 3 4 5 6025 5 6 7 8 9 32221 5 10 11 12 13 39240 5 14 15 16 17 55392 5 18 19 20 21 69386 ...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100000 10 5 11 12 13 14 15 3 66 67 68 4 96 97 98 99 5 1274 1643 2223 2242 2626 5 5407 8119 10748 198...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
100000 10 5 11 12 13 14 15 3 66 67 68 4 98 99 100 101 5 193 213 239 613 1656 5 187 259 453 513 3129 ...