Submission #956277
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
#include <sys/time.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define REP(i,n) FOR(i,0,n)
#define each(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
#define sz(s) (int)((s).size())
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(x,y) make_pair((x),(y))
double pi=3.14159265358979323846;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";
REP(i,z.size())os << z[i] << ", " ;
return ( os << "]" << endl);
}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( ";
EACH(p,z)os << (*p) << ", " ;
return ( os << ")" << endl);
}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ ";
EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;
return ( os << "}" << endl);
}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );
}
double get_time(){
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec*1e-6;
}
typedef unsigned int uint32_t;
struct RND{
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
RND(){
x=123456789;
y=362436069;
z=521288629;
w=88675123;
}
void init(int seed){
x=123456789;
y=362436069;
z=521288629;
w=seed+100;
REP(i,10)get();
}
uint32_t get(){
uint32_t t;
t=x^(x<<11);
x=y;y=z;z=w;
w=(w^(w>>19))^(t^(t>>8));
return w;
}
};
RND rnd;
int N,M;
vvl s[2];
vl visit;
vl color;
bool black; // 色の区別がなくなってしまった。
bool bomb; // 爆発したかどうか?
ll edge_num; // 爆発しないときに使用。
ll cnt[3]; // 各色の頂点数
void rec(int v, int c){
//deb(v);deb(c);debl;
if(visit[v]){
if(c!=color[v]){
black = true;
}
return;
}
if(s[0][v].size()>0 && s[1][v].size()>0){
if(!(s[0][v].size()==1 && s[1][v].size()==1 && s[0][v][0]==v ))bomb = true;
}
color[v]=c;
visit[v]=1;
cnt[c]++;
rep(b,2){
rep(ii, s[b][v].size()){
edge_num++;
int v2 = s[b][v][ii];
int c2 = (c+b+1)%3;
rec(v2, c2);
}
}
}
void _main(istream &inp){
inp >> N >>M;
rep(b,2){
s[b] = vvl(N);
}
visit = vl(N);
color = vl(N, -1);
rep(i,M){
int a,b;
inp >> a >> b;
a--;
b--;
s[0][a].push_back(b);
s[1][b].push_back(a);
}
ll ret = 0;
rep(v,N){
if(visit[v]==0){
black = false ; // 色の区別がなくなってしまった。
bomb = false; // 爆発したかどうか?
edge_num = 0 ; // 爆発しないときに使用。
rep(k,3)cnt[k]=0; // 各色の頂点数
rec(v,0);
if(!bomb){
ret += edge_num/2;
}
else{
if(!black){
ret += cnt[0]*cnt[1] + cnt[1]*cnt[2] + cnt[2]*cnt[0];
}
else{
ret += ( cnt[0] + cnt[1] + cnt[2] ) * ( cnt[0] + cnt[1] + cnt[2] );
}
}
//deb(v);
//deb(black);
//deb(bomb);
//deb(edge_num);
//debl;
}
}
cout << ret << endl;
while(true){
break;
}
}
int main(){
if(0){
ifstream ifs("test.txt");
_main(ifs);
}
else{
_main(cin);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Blackout |
User |
hirosegolf |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
4405 Byte |
Status |
AC |
Exec Time |
111 ms |
Memory |
19072 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1700 / 1700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
256 KB |
0_01.txt |
AC |
3 ms |
256 KB |
0_02.txt |
AC |
2 ms |
256 KB |
1_00.txt |
AC |
2 ms |
256 KB |
1_01.txt |
AC |
10 ms |
6528 KB |
1_02.txt |
AC |
90 ms |
12800 KB |
1_03.txt |
AC |
97 ms |
18944 KB |
1_04.txt |
AC |
97 ms |
18944 KB |
1_05.txt |
AC |
99 ms |
19072 KB |
1_06.txt |
AC |
99 ms |
18944 KB |
1_07.txt |
AC |
96 ms |
18944 KB |
1_08.txt |
AC |
97 ms |
18944 KB |
1_09.txt |
AC |
97 ms |
18944 KB |
1_10.txt |
AC |
98 ms |
18944 KB |
1_11.txt |
AC |
96 ms |
18944 KB |
1_12.txt |
AC |
97 ms |
18944 KB |
1_13.txt |
AC |
93 ms |
15872 KB |
1_14.txt |
AC |
75 ms |
10356 KB |
1_15.txt |
AC |
74 ms |
10356 KB |
1_16.txt |
AC |
75 ms |
10352 KB |
1_17.txt |
AC |
57 ms |
2816 KB |
1_18.txt |
AC |
103 ms |
12288 KB |
1_19.txt |
AC |
103 ms |
12288 KB |
1_20.txt |
AC |
109 ms |
12160 KB |
1_21.txt |
AC |
103 ms |
12288 KB |
1_22.txt |
AC |
103 ms |
12288 KB |
1_23.txt |
AC |
102 ms |
12288 KB |
1_24.txt |
AC |
101 ms |
12160 KB |
1_25.txt |
AC |
103 ms |
12288 KB |
1_26.txt |
AC |
103 ms |
12160 KB |
1_27.txt |
AC |
101 ms |
12160 KB |
1_28.txt |
AC |
101 ms |
12288 KB |
1_29.txt |
AC |
110 ms |
12288 KB |
1_30.txt |
AC |
103 ms |
12032 KB |
1_31.txt |
AC |
100 ms |
12160 KB |
1_32.txt |
AC |
101 ms |
12288 KB |
1_33.txt |
AC |
104 ms |
12288 KB |
1_34.txt |
AC |
100 ms |
10624 KB |
1_35.txt |
AC |
110 ms |
7936 KB |
1_36.txt |
AC |
102 ms |
9600 KB |
1_37.txt |
AC |
111 ms |
11648 KB |
1_38.txt |
AC |
91 ms |
6912 KB |
1_39.txt |
AC |
87 ms |
6400 KB |
1_40.txt |
AC |
106 ms |
12032 KB |
1_41.txt |
AC |
104 ms |
11776 KB |
1_42.txt |
AC |
90 ms |
8704 KB |
1_43.txt |
AC |
94 ms |
8192 KB |
1_44.txt |
AC |
100 ms |
10752 KB |
1_45.txt |
AC |
85 ms |
5632 KB |
1_46.txt |
AC |
101 ms |
11264 KB |
1_47.txt |
AC |
101 ms |
11776 KB |
1_48.txt |
AC |
93 ms |
7552 KB |
1_49.txt |
AC |
97 ms |
9344 KB |