QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554089 | #2751. Find Poly | Tenshi# | AC ✓ | 1ms | 4216kb | C++20 | 1.6kb | 2024-09-09 05:11:34 | 2024-09-09 05:11:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
inline void read(int &x){
int s=0; x=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
// set<pii> st;
map<pii, int> mp;
int tot;
struct Seg{
pii a, b;
};
vector<Seg> seg;
const int N=1e5+5;
int deg[N];
int f[N];
int find(int x){
return f[x]==x? x: f[x]=find(f[x]);
}
bool ng[N];
signed main(){
rep(i, 1, N-1) f[i]=i;
string s;
while(getline(cin, s)){
int cur=0;
int n=s.size();
vector<int> buf;
rep(i, 1, n-1){
if(isdigit(s[i])){
cur=cur*10+(s[i]-'0');
}
else if(isdigit(s[i-1])){
buf.pb(cur);
cur=0;
}
}
for(int i=0; i<buf.size(); i+=4){
pii fir={buf[i], buf[i+1]};
pii sec={buf[i+2], buf[i+3]};
if(!mp.count(fir)) mp[fir]=++tot;
if(!mp.count(sec)) mp[sec]=++tot;
int u=mp[fir], v=mp[sec];
// seg.pb({buf[i], buf[i+1]});
deg[u]++;
deg[v]++;
f[find(u)]=find(v);
}
}
int fir=0, sec=0;
rep(i, 1, tot){
if(i==find(i)){
fir++;
}
if(deg[i]!=2) ng[find(i)]=true;
}
// debug(tot);
// rep(i, 1, tot) debug(deg[i]);
rep(i, 1, tot) if(i==find(i) && !ng[i]) sec++;
cout<<fir<<" "<<sec<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
(0,0),(0,10);(0,0),(5,5);(0,10),(5,5); (10,0),(10,10);(10,0),(5,5);(10,10),(5,5); (20,20),(21,21); (30,30),(35,30);(35,30),(35,35);
output:
3 0
result:
ok single line: '3 0'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
(12,10),(23,47); (18,9),(12,10); (21,9),(18,9); (23,47),(34,16); (23,85),(33,98); (25,77),(23,85); (33,98),(49,75); (34,16),(16,34); (34,16),(21,9); (46,73),(25,77); (52,40),(91,80); (81,35),(52,40); (91,80),(98,59); (98,56),(81,35); (98,59),(98,56);
output:
3 1
result:
ok single line: '3 1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
(0,65),(21,57); (19,55),(5,54); (21,57),(19,55); (21,57),(57,21); (2,18),(27,44); (24,8),(3,15); (2,56),(2,57); (2,57),(0,65); (27,44),(30,42); (30,42),(35,37); (3,15),(2,18); (33,82),(43,93); (35,37),(24,8); (43,93),(69,85); (5,54),(2,56); (55,56),(33,82); (59,38),(68,15); (59,51),(71,58); (63,6),(...
output:
6 2
result:
ok single line: '6 2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4012kb
input:
(11,33),(23,34); (21,86),(21,87); (21,87),(22,89); (22,83),(22,84); (22,84),(21,86); (22,89),(23,93); (23,34),(24,33); (23,93),(28,97); (24,33),(25,33); (25,33),(27,31); (27,31),(35,17); (28,97),(34,98); (29,76),(22,83); (31,75),(29,76); (32,75),(31,75); (33,75),(32,75); (34,75),(33,75); (34,98),(35...
output:
6 3
result:
ok single line: '6 3'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
(45,26),(88,34);(92,38),(73,52);(63,35),(18,61);(73,52),(85,59);(86,47),(2,75); (26,18),(95,36);(8,19),(67,8);(59,78),(49,95);(39,6),(85,7);(67,80),(63,95); (33,46),(23,12);(33,1),(46,10);(63,78),(2,75);(11,31),(2,33);(81,30),(44,76); (18,5),(99,98);(86,47),(67,8);(49,95),(88,34);(82,51),(81,30);(86...
output:
5 1
result:
ok single line: '5 1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
(63,74),(43,89);(49,82),(73,90);(56,93),(47,34);(0,52),(20,90);(26,18),(95,36); (67,80),(63,95);(8,51),(29,44);(33,1),(46,10);(22,50),(66,57);(11,31),(2,33); (81,30),(44,76);(99,98),(18,5);(82,51),(81,30);(30,61),(81,4);(47,22),(53,10); (39,67),(79,70);(29,42),(96,2);(24,23),(13,3);(41,29),(99,39);(...
output:
3 0
result:
ok single line: '3 0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
(43,89),(63,74);(49,82),(73,90);(56,93),(47,34);(20,90),(0,52);(95,36),(26,18); (67,80),(63,95);(33,1),(46,10);(2,33),(11,31);(81,30),(44,76);(99,98),(18,5); (81,30),(82,51);(30,61),(81,4);(53,10),(47,22);(39,67),(79,70);(96,2),(29,42); (41,29),(99,39);(41,40),(28,7);(98,88),(13,89);(46,7),(46,10);(...
output:
1 0
result:
ok single line: '1 0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4216kb
input:
(12,17),(99,92); (99,92),(26,61); (26,61),(85,99); (85,99),(67,47); (67,47),(71,50); (71,50),(64,51); (64,51),(27,3); (27,3),(80,26); (80,26),(49,76); (49,76),(4,79); (4,79),(70,66); (70,66),(82,74); (82,74),(26,11); (26,11),(75,6); (75,6),(49,60); (49,60),(27,77); (27,77),(69,37); (69,37),(85,63); ...
output:
1 0
result:
ok single line: '1 0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4184kb
input:
(89,68),(65,41); (65,41),(21,50); (21,50),(95,89); (95,89),(50,64); (50,64),(56,45); (56,45),(76,45); (76,45),(4,59); (4,59),(4,84); (4,84),(32,30); (32,30),(82,44); (82,44),(2,29); (2,29),(8,66); (8,66),(69,40); (69,40),(90,89); (90,89),(42,96); (42,96),(94,64); (94,64),(90,95); (90,95),(10,38); (1...
output:
1 0
result:
ok single line: '1 0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4000kb
input:
(31,90),(38,76); (38,76),(32,3); (32,3),(50,74); (50,74),(96,96); (96,96),(13,49); (13,49),(26,49); (26,49),(28,94); (28,94),(57,7); (57,7),(87,84); (87,84),(9,62); (9,62),(30,26); (30,26),(82,90); (82,90),(97,36); (97,36),(76,88); (76,88),(91,53); (91,53),(32,86); (32,86),(42,35); (42,35),(93,61); ...
output:
1 1
result:
ok single line: '1 1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
(84,84),(78,84);(68,60),(64,64);(20,85),(15,88);(0,0),(2,8); (30,60),(30,66);(13,40),(18,38);(15,88),(15,95);(18,38),(8,38); (31,7),(25,10);(30,66),(26,70);(40,14),(30,19);(5,85),(15,88); (48,20),(56,26);(84,84),(84,82);(66,82),(70,86);(15,95),(25,90); (70,86),(66,88);(59,23),(50,27);(15,88),(5,80);...
output:
10 4
result:
ok single line: '10 4'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
(45,26),(88,34);(39,6),(67,8);(73,52),(92,38);(63,35),(18,61); (34,23),(46,10);(2,75),(86,47);(26,18),(95,36);(59,78),(49,95); (63,95),(67,80);(23,12),(33,46);(33,1),(46,10);(63,78),(2,75); (2,33),(11,31);(99,98),(18,5);(88,34),(49,95);(25,43),(46,10); (66,1),(2,75);(17,59),(2,33);(85,7),(85,59);(51...
output:
7 2
result:
ok single line: '7 2'